本文最后更新于 1163 天前，其中的信息可能已经有所发展或是发生改变。
代码语言：javascript复制#include<iostream>
using namespace std;
#define INF 1000000
int n;
int arr[100][100];
int s[100];
int dist[100];
int path[100];
void f(int v0){
for(int i=0;i<n;i ){
dist[i]=arr[v0][i];
s[i]=0;
if(dist[i]!=INF&&i!=v0){
path[i]=v0;
}else{
path[i]=-1;
}
}
dist[v0]=0;
s[v0]=1;
for(int i=0;i<n-1;i ){
int MIN=INF;
int v=v0;
for(int j=0;j<n;j ){
if(MIN>dist[j]&&s[i]==0){
MIN=dist[i];
v=i;
}
}
s[v]=1;
for(int j=0;j<n;j ){
if(arr[v][j]!=INF&&s[j]==0&&arr[v][j] dist[v]<dist[j]){
dist[j]=arr[v][j] dist[v];
path[j]=v;
}
}
}
}
int main(){
cin>>n;
for(int i=0;i<n;i ){
for(int j=0;j<n;j ){
if(i==j){
arr[i][j]=0;
}else{
arr[i][j]=INF;
}
}
}
int x,y,v;
cin>>x>>y>>v;
while(1){
arr[x][y]=v;
cin>>x>>y>>v;
if(x==-1&&y==-1&&v==-1){
break;
}
}
int v0,vn;
cin>>v0>>vn;
f(v0);
int shortest[n];
shortest[0]=vn;
int i=0;
while(path[shortest[i]]!=v0){
i ;
shortest[i]=path[shortest[i-1]];
}
i ;
shortest[i]=v0;
for(int j=i;j>=0;j--){
cout<<shortest[j]<<" ";
}
return 0;
}Post Views: 251
