提出 #76529051

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
typedef long long li;
const int maxn=310005;
li dis[maxn];
li cnt[maxn];
bool vis[maxn];
struct point {
	int n;
	vector <int> to;
	vector <li> w;
} a[maxn];
struct p {
	li first;
	li second;
	friend bool operator < (p a, p b) {
		return a.first<b.first;
	}
	friend bool operator > (p a, p b) {
		return a.first>b.first;
	}
	friend bool operator == (p a, p b) {
		return a.first==b.first;
	}
};
priority_queue <p, vector<p>, greater<p> > q;
li n, m, s;
int main() {
	cin.tie (0);
	cin >> n >> m;
	s=1;
	for (int i=1; i<=m; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		a[x].n++;
		a[x].to.push_back (y);
		a[x].w.push_back (z);
		a[y].n++;
		a[y].to.push_back (x);
		a[y].w.push_back (z);
	}
	for(int i=2;i<=n;i++)dis[i]=0x3f3f3f3f3f3f3f3f;
	q.push ({0, s});
	while (q.size()) {
		li u=q.top().second;
		q.pop();
		if (vis[u]) { continue; }
		vis[u]=1;
		for (int ind=0; ind< (int)a[u].n; ind++) {
			int v=a[u].to[ind];
			li w=a[u].w[ind];
			if (dis[v]>dis[u]+w) {
				dis[v]=dis[u]+w;
				q.push ({dis[v], v});
				//	cnt[p.v]=cnt[u]+1;
				//	if(cnt[p.v]>=n) {
				//	cerr << "Negative loop!";
				//	exit(2);
				//	}
				//	if(!vis[p.v]) {
				//	q.push(p.v);
				//	vis[p.v]=1;
				//	}
			}
		}
	}
	if(dis[n]<0X3FFFFFFFFFFFFFF)cout<<dis[n];
	else cout<<-1;
}

提出情報

ジャッジ結果