P3371 【模板】单源最短路径（弱化版）

 链表形式的dij解决最短路径问题

#include<bits/stdc++.h>
using namespace std;
const int MAXV=10005;
const int INF=2147483647;
typedef long long ll;
struct Node{
	int ed;
	ll dis;
};

vector<Node> ft[MAXV];
bool vis[MAXV]={false};
ll d[MAXV];
int n,m,s;

void dij(){
	fill(d,d+MAXV,INF);
	d[s-1]=0;
	for(int i=0;i<n;i++){
		int u=-1;ll MIN=INF;
		for(int j=0;j<n;j++){
			if(vis[j]==false&&d[j]<MIN){
				u=j;MIN=d[j];
			}
		}
		if(u==-1) return;
		vis[u]=true;
		for(int j=0;j<ft[u].size();j++){
			int t=ft[u][j].ed;
			if(vis[t]==false&&d[t]>d[u]+ft[u][j].dis){
				d[t]=d[u]+ft[u][j].dis;
			}
		}
	}
}
int main()
{
	freopen("in.txt","r",stdin);
	cin>>n>>m>>s;
	for(int i=0;i<m;i++){
		int st,edd;ll cost;cin>>st>>edd>>cost;
		st=st-1;edd=edd-1;
		Node t1;
		t1.ed=edd;
		t1.dis=cost;
		ft[st].push_back(t1);
	}
	dij();
	for(int i=0;i<n;i++){
		if(i==s-1) cout<<0<<' ';
		else{
			if(d[i]>=INF) cout<<2147483647<<' ';
			else cout<<d[i]<<' ';
		} 
	}
	return 0;
}