松弛操作
我们改变松弛操作为d[v]=min(d[u],e.cost)
并维护一个大顶堆。
注意输出格式
代码如下:
#include<iostream> #include<algorithm> #include<queue> #include<cstdio> using namespace std; typedef pair<int, int> pii; const int inf = 2e9; const int max_n = 1100; const int max_m = 1e6 + 100; struct edge{ int to, cost, next; }E[max_m << 1]; int head[max_n]; int cnt = 1; void add(int from, int to, int cost) { E[cnt].to = to;E[cnt].cost = cost; E[cnt].next = head[from];head[from] = cnt++; } int d[max_n]; int dijstra(int s,int t) { priority_queue<pii> que; fill(d, d + max_n, -inf); d[s] = inf; que.push(make_pair(d[s], s)); while (!que.empty()) { pii p = que.top();que.pop(); int u = p.second;int dist = p.first; if (dist < d[u])continue; for (int i = head[u];i;i = E[i].next) { edge& e = E[i]; if (d[e.to] < min(d[u], e.cost)) { d[e.to] = min(d[u], e.cost); que.push(make_pair(d[e.to], e.to)); } } }return d[t]; } int N, M; int main() { int tcase;scanf("%d", &tcase); for (int t = 1;t <= tcase;++t) { fill(head, head + max_n, 0);cnt = 1; scanf("%d %d", &N, &M); for (int i = 1, u, v, w;i <= M;++i) { scanf("%d %d %d", &u, &v, &w); add(u, v, w);add(v, u, w); }printf("Scenario #%d:\n%d\n\n", t, dijstra(1, N)); } }