题解 | #最短路#

最短路径，一维

using namespace std;
const int inf=1e9+5;
int v[200005],u[200005],w[200005];
int d[20005];
int main(){
	int n,m,f;
	cin>>n>>m;
	memset(d,inf,sizeof(d));
	d[1]=0;
	for(int i=1;i<=m;i++)
	cin>>v[i]>>u[i]>>w[i];
	for(int i=1;i<=n;i++)
	{
		f=0;
		for(int k=1;k<=m;k++)
		{
			if(d[v[k]]>=1e9/2) continue;
			if(d[u[k]]>d[v[k]]+w[k])
			f=1,d[u[k]]=d[v[k]]+w[k];
		}
		if(f==0)
		break;
	}
	for(int i=2;i<=n;i++)
	cout<<d[i]<<endl;
	return 0;
}