还没学vector
来搞最短路,用的邻接矩阵,不知道为啥WA o(TヘTo)
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
ll val[1001][1001];
ll dis[1001],vis[1001];
#define inf ll(1<<30)*2-1 // 2147483647
ll n,m,s;
void init(){
for(ll i=1;i<=n;i++){for(ll j=1;j<=n;j++){if(i==j)val[i][j]=0;else val[i][j]=inf;}}
}
void input(){
while(m--){
ll u,v,w;
cin>>u>>v>>w;
val[u][v]=w;
}
}
void dijkstra(){
vis[s]=1;
for(ll i=1;i<=n;i++)dis[i]=val[s][i];
ll k;
for(ll i=1;i<n;i++){
ll nmin=inf;
for(ll j=1;j<=n;j++){
if(!vis[j] and nmin>dis[j]){nmin=dis[j];k=j;}
}
vis[k]=1;
for(ll j=1;j<=n;j++){
if(!vis[j] and dis[j]>dis[k]+val[k][j])dis[j]=dis[k]+val[k][j];
}
}
}
int main(){
cin>>n>>m;
cin>>s;
init();
input();
dijkstra();
for(ll i=1;i<=n;i++)cout<<dis[i]<<" ";
return 0;
}