题解 P3020 【[USACO11MAR]包快递Package Delivery】

寒鸽儿 · 2019-04-11 16:00:12 · 题解

dijkstra裸题？
直接跑模板好了。
建议使用if(dnow > d[cur]) continue; 来代替if(!vis[cur]),据说这样子更加快一些
72ms

#include <cstdio>
#include <cstring>
#include <queue>
#define pii pair<int, int>

using namespace std;

const int maxn = 50010;

priority_queue<pii> q;
int n;

#define gc() getchar()
char buf[2000000];
inline void read(int &x) {
    x = 0;
    char ch = gc();
    while( ch < '0' || ch > '9' ) ch = gc();
    while(ch >= '0' && ch <= '9') x = (x<<3)+(x<<1)+(ch&15), ch = gc();
}

int head[maxn], ver[maxn<<1], wei[maxn<<1], nex[maxn<<1], tot = 0;
inline void addedge(int u, int v, int w) {
    ver[tot] = v; wei[tot] = w; nex[tot] = head[u]; head[u] = tot++;
    ver[tot] = u; wei[tot] = w; nex[tot] = head[v]; head[v] = tot++;
}

int d[maxn];

int main() {
    int m, u, v, w;
    memset(head, -1, sizeof(head));
    memset(d, 0x3f, sizeof(d));
    read(n); read(m);
    while(m--) {
        read(u); read(v); read(w);
        addedge(u, v, w);
    }
    d[1] = 0; q.push(make_pair(0, 1));
    while(!q.empty()) {
        int cur = q.top().second, dmen = -q.top().first; q.pop();
        if(dmen > d[cur]) continue;
        for(int i = head[cur]; i != -1; i = nex[i])
            if(d[ver[i]] > d[cur] + wei[i]) {
                d[ver[i]] = d[cur] + wei[i];
                q.push(make_pair(-d[ver[i]], ver[i]));
            }
    }
    printf("%d\n", d[n]);
    return 0;
}

欢迎互相关注(然而在oi界蒟蒻的圈很小)。
最后安利一下蒟蒻的洛谷博客