链式前向星+dijkstra 40pts

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=2147483647;
long long dis[10010];
bool book[10010];
int n,m,s;
struct node{
    long long v;
    int to;
    int nxt;
}b[10010];
int head[10010],cnt=0;
void add(int x,int y,long long t){
    cnt++;
    b[cnt].to=y;
    b[cnt].nxt=head[x];
    b[cnt].v=t;
    head[x]=cnt;
    return;
}
int main(){
	cin>>n>>m>>s;
	for(int i=1;i<=m;i++){
		int p,q,t;
		cin>>p>>q>>t;
		add(p,q,t);
	}
	for(int i=1;i<=n;i++){
	    dis[i]=inf;
	}
// 	for(int i=head[s];i!=0;i=b[i].nxt){
// 	    dis[b[i].to]=b[i].v;
// 	}
	dis[s]=0;
	int u=s;
	while(!book[u]){
	    book[u]=1;
		for(int j=head[u];j!=0;j=b[j].nxt){
		    if(!book[b[j].to]&&dis[b[j].to]){
		        dis[b[j].to]=min(dis[u]+b[j].v,dis[b[j].to]);
		    }
		}
		long long minn=inf;
		for(int j=1;j<=n;j++){
			if(!book[j]&&dis[j]<minn){
				minn=dis[j];
				u=j;
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}