最短路径test

#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;
}