Dijkstra，60分，WA#2#6#9#10

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

const int INF=(2<<30)-1;
int n,m,s,u,v,w,minn,org,next_org,cnt;
struct Edge{
	int v,w;
	Edge(int v,int w):v(v),w(w){}
};
vector<Edge> adj[10005];
bool S[10005];
int dis[10005];

int main(){
	cin>>n>>m>>s;
	cnt=n;
	for(int i=1;i<=n;i++){
		dis[i]=INF;
	}
	for(int i=1;i<=m;i++){
		cin>>u>>v>>w;
		adj[u].push_back(Edge(v,w));
	}
	int org=s;
	dis[org]=0;
	S[org]=true;
	while(cnt>0){
		minn=INF;
		next_org=-1;
		for(int j=0;j<adj[org].size();j++){
			if(S[adj[org][j].v]==0){
				dis[adj[org][j].v]=min(dis[adj[org][j].v],dis[org]+adj[org][j].w);
				if(minn>=dis[adj[org][j].v]){
					next_org=adj[org][j].v;
				}
				minn=min(dis[adj[org][j].v],minn);
			}
		}
		if(next_org==-1){
			break;
		}
		S[next_org]=true;
		org=next_org;
		cnt--; 
	}
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
	}
	return 0;
}

orz