AndyCGM @ 2024-03-22 06:35:13
#include <iostream>
#include <cmath>
using namespace std;
int map[10100][10100];
int inf=0x3f3f3f3f;
int n,m,s;
int solve(int start){
//Get ready.
int result[10100],lastpoint[10100]={0},vis[10100]={0};
for (int i=1; i<=n; i++) result[i]=inf;
result[start]=0;
lastpoint[start]=start;
//Start the main topic.
for (int trytime=1; trytime<=n; trytime++){
int sv=inf;//Smallest value
int svi=0;//Snakkest value's index
//Find the dot's ax vallue is smallest
for (int index=1; index<=n; index++){
if (result[index]<sv && vis[index]==0){
sv=result[index];
svi=index;
}
}
int i=svi;
for (int j=1; j<=n; j++){
//If the dots i,j are connected dirrectly and i was unsettled.
if (map[i][j]!=0 && vis[j]==0){
//Caculate the Aproxed shortest way.
int approx=result[i]+map[i][j];
//If we find a better way, then we change the approx anwser.
if (approx<result[j]){
result[j]=approx;
lastpoint[j]=i;
}
}
}
//Settle this point
vis[i]=1;
}
for (int i=1; i<=n; i++){
if (result[i]==inf) cout << -1;
else cout << result[i];
cout << " ";
}
}
int main(){
cin >> n >> m >> s;
for (int i=1; i<=m; i++){
int u,v,w;
cin >> u >> v >> w;
if (map[u][v]==0){
map[u][v]=w;
}else{
if (w<map[u][v]){
map[u][v]=w;
}
}
}
solve(s);
return 0;
}
by Tomle @ 2024-03-22 06:54:57
数组开大了,别用邻接矩阵
by InversionShadow @ 2024-03-22 07:47:09
@AndyChen130130
by _yukinoshita_yukino @ 2024-04-19 09:48:24
用堆优化
by Kevin1027 @ 2024-06-23 16:57:10