Submission #59020980

---

Source Code Expand

#include <bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using namespace atcoder;
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef pair<ll,ll> P;
typedef modint1000000007 mi;
constexpr ll mod=1000000007;

struct edge{
	ll to,cost;
};

vector<edge>G[100005];

vector<ll> dijkstra(int s,int N){
	vector<ll>d(N,1e18);
	d[s]=0;
	priority_queue<P,vector<P>,greater<P>>Q;
	Q.push({0,s});

	while(Q.size()){
		P p=Q.top();
		Q.pop();
		int v=p.second;
		if(d[v]<p.first)continue;

		for(auto e:G[v]){
			if(d[e.to]>d[v]+e.cost){
				d[e.to]=d[v]+e.cost;
				Q.push({d[e.to],e.to});
			}
		}
	}
	return d;
}

int main(){
	int n,m;cin>>n>>m;
	rep(i,m){
		ll a,b,c;
		cin>>a>>b>>c;
		a--;b--;
		G[a].push_back({b,c});
		G[b].push_back({a,c});
	}
	vector<ll>d0=dijkstra(0,n),dn=dijkstra(n-1,n);

	rep(i,n){
		cout<<d0[i]+dn[i]<<endl;
	}

}

Submission Info

Judge Result