1223: 最短路(dijkstra算法)

输入


第一行两个正整数n，m用空格隔开(n≤100，m≤1000)代表n个顶点，m条边。

接下来m行每行三个整数u，v，w代表有一条权值为w的边从u到v，(1≤u,v≤n，1≤w≤100000)可能含有重边。

样例解释如上。

输出


一行n个数，含义如题目描述。

样例输入


6 10

1 2 3

3 4 2

2 4 7

1 3 4

1 4 3

1 5 10

2 5 4

5 6 5

5 3 2

2 6 1

样例输出


0 3 4 3 7 4

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
const ll maxn=1e3+10;
const ll inf=0x3f3f3f;
int n,m;
struct edge{
	int to;
	int cost;
};
vector<edge> g[maxn];
int d[maxn];
void dij(int s){
	fill(d,d+n+100,inf);
	d[s]=0;
	priority_queue<P,vector<P>,greater<P> > que;
	que.push({d[s],s});
	while(!que.empty()){
		P pp=que.top();
		que.pop();
		int v=pp.second;
		//int w=pp.first;
		if(d[v]<pp.first)continue;
		for(int i=0;i<g[v].size();i++){
			edge e=g[v][i];
			if(d[e.to]>(d[v]+e.cost)){
				//cout<<u<<" "<<v<<endl;
				//cout<<u<<" "<<d[v]<<" "<<ww<<endl;
				d[e.to]=d[v]+e.cost;
				//cout<<d[v]<<" "<<ww<<" "<<u<<" "<<d[u]<<endl;
				que.push({d[e.to],e.to});
			}
		}
	}
}
int main(){
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back({v,w});
	}
	dij(1);
	for(int i=1;i<=n;i++){
		printf("%d ",d[i]);
	}
	return 0;
}