自动搬运

查看原文

来自洛谷，原作者为

	寒鸽儿 寒鸽儿gugugu~

搬运于2025-08-24 21:44:28，当前版本为作者最后更新于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界蒟蒻的圈很小)。
最后安利一下蒟蒻的洛谷博客