题意就不再赘述了
黑书上308页例1是极其相似的题。。。。
思路也一样
枚举每个点作为吃饭的地点。
每次以枚举的这个点为起点做最短路,途中不能走比它贵的点。
每次求出最短路后要更新我们的查询答案。更新其实也就是一行的样子。
假设查询的两个点有个最优的方案,那么路径上有某点是吃饭的地点,那么从该点出发按刚才的方法一定能找到查询的那两个点。
据称本题卡常数,我最后用了3400ms 的样子。
那么尽量不要用stl的东西了。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 1005
#define MAXM 40005
#define INF 10000000000007LL
using namespace std;
struct EDGE
{
int v, next, w;
}edge[MAXM];
int head[MAXN], e;
void init()
{
memset(head, -1, sizeof(head));
e = 0;
}
void add(int x, int y, int w)
{
edge[e].v = y;
edge[e].w = w;
edge[e].next = head[x];
head[x] = e++;
}
long long d[MAXN], ans[MAXM];
int a[MAXM], b[MAXM], val[MAXN];
int que[MAXM * 5], vis[MAXN];
int q, n, m;
void spfa(int src)
{
for(int i = 0; i <= n; i++) d[i] = INF, vis[i] = 0;
int h = 0, t = 0;
vis[src] = 1;
d[src] = 0;
que[t++] = src;
while(h < t)
{
int u = que[h++];
vis[u] = 0;
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if(val[v] <= val[src] && d[u] + edge[i].w < d[v])
{
d[v] = d[u] + edge[i].w;
if(!vis[v])
{
vis[v] = 1;
que[t++] = v;
}
}
}
}
for(int i = 1; i <= q; i++)
if(d[a[i]] != INF && d[b[i]] != INF && ans[i] > d[a[i]] + d[b[i]] + val[src])
ans[i] = d[a[i]] + d[b[i]] + val[src];
}
int main()
{
while(scanf("%d%d", &n, &m) != EOF)
{
if(!n && !m) break;
init();
int u, v, w;
for(int i = 1; i <= n; i++) scanf("%d", &val[i]);
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d", &u, &v, &w);
add(u, v, w), add(v, u, w);
}
scanf("%d", &q);
for(int i = 1; i <= q; i++)
{
scanf("%d%d", &a[i], &b[i]);
ans[i] = INF;
}
for(int i = 1; i <= n; i++) spfa(i);
for(int i = 1; i <= q; i++)
{
if(ans[i] == INF) printf("-1\n");
else printf("%lld\n", ans[i]);
}
puts("");
}
return 0;
}
分享到:
相关推荐
POJ2009年最新版,相当详细.................
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
poj 2744子串 答案 所用的是最简单的C语言
POJ2968代码有用,欢迎下载,POJ代码
poj 1440解题报告 poj 1440解题报告 poj 1440解题报告 poj 1440解题报告