//Algorithm=Dijkstra
/*
Input-1
6 9 1
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
Output-1
1->2:1
1->3:8
1->3:4
1->4:13
1->5:17
-------------------------------
Input-2
6 9 1
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
Output-2

*/

#include<bits/stdc++.h>
#include<windows.h>
using namespace std;

int main()
{
	int dis[1001],book[1001],i,j,n,m,t1,t2,t3,fu,fv,min,f,e=0,pos;
	int first[1001],next[1001];
	int u[1001],v[1001],w[1001];
	const int inf=99999999;
	cin>>n>>m>>f;
	//Init Graph
	for(int i=1;i<=m;i++){
		next[i]=-1;
		first[i]=-1;
	}
	//Add Edges
	for(i=1; i<=m; i++)
	{
		cin>>t1>>t2>>t3;
		e+=1;
		u[e]=t1;
		v[e]=t2;
		w[e]=t3;
		next[e]=first[u[e]];
		first[u[e]]=e;
	}
	//Init Answers
	for(int i=1;i<=n;i++){
		dis[i]=inf;
	}
	dis[f]=0; 
	pos=first[f];
	while(pos!=-1){
		dis[pos]=w[pos];
		pos=next[pos];
	}
	//Init Flags
	for(i=1; i<=n; i++){
		book[i]=0;
	}
	book[f]=1;
	//Dijkstra Core
	for(int i=1;i<=n-1;i++){
		min=inf;
		for(int j=1;j<=n;j++){
			if(book[j]==0 && dis[j]<min){ 
				min=dis[j]; 
				fu=j;
			}
		}
		book[fu]=1;
		pos=first[fu];
		while(pos!=-1){
			if(w[pos]<inf){
				if(dis[v[pos]]>dis[fu]+w[pos]) dis[v[pos]]=dis[fu]+w[pos];
			}
			pos=next[pos];
		}
	}
	//Output Answer
	for(int i=1;i<=n;i++){
		printf("%d->%d:%d\n",f,i,dis[i]);
	}
	return 0;
}

以上是邻接表写的dijkstra,请帮忙看错