Heavy Transportatio

松弛操作

我们改变松弛操作为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));
    }
}