パスのリストア
1550 ワード
#include
#include
#include
#include
#include
#define INF 999999
using namespace std;
int G[203][203];
int n, s, t;
bool Dijkstra()
{
int i, j, k;
int dis[203];
bool vis[203];
int pre[203];//
memset(vis,false,sizeof(vis));
fill(dis,dis+n,INF);
memset(pre,-1,sizeof(pre));// -1
dis[s] = 0;
for(i=0;idis[j]))
k = j;
if(k == -1)
break;
vis[k] = true;
for(j=0;jdis[k]+G[k][j]){
dis[j] = dis[k]+G[k][j];
pre[j] = k;//
}
}
printf("%d——>%d :",s,t);
printf("%d
",dis[t]);
printf(" :");
//
stackque;
for(t;t!=-1;t=pre[t])// t s
que.push(t);//
printf("%d",que.top());//
que.pop();//
while(!que.empty()){
printf("——>%d",que.top());//
que.pop();//
}
printf("
");
}
int main()
{
int i, j, u, v, w, m;
while(scanf("%d %d",&n,&m)==2){
for(i=0;iw)
G[u][v] = G[v][u] = w;
}
scanf("%d %d",&s,&t);
Dijkstra();
}
return 0;
}
/*
3 3
0 1 1
0 2 3
1 2 1
0 2
2
0->1->2
*/