Code: Select all
#include <iostream>
using namespace std;
#include <cstdio>
#include <cstring>
#define MAXV 100
#define MAXDEGREE 100
#define MAXINT 99999
int parent[MAXV];
int del[MAXV][MAXV];
int cas=1;
typedef struct
{
int v;
int weight;
}edge;
typedef struct
{
edge edges[MAXV+1][MAXDEGREE];
int degree[MAXV+1];
int nvertices;
}graph;
void init(graph *g,int n)
{
int i,j;
int x,y,z;
for(i=1;i<=MAXV;i++)
g->degree[i]=0;
g->nvertices=n;
for(i=1;i<=g->nvertices;i++)
{
cin>>z;
for(j=0;j<z;j++)
{
cin>>x>>y;
del[i][x]=y;
g->edges[i][g->degree[i]].v=x;
g->edges[i][g->degree[i]].weight=y;
g->degree[i]++;
}
}
}
void dijkstra(graph *g,int start)
{
int i;
bool intree[MAXV];
int distance[MAXV];
int v;
int w;
int weight;
int dist;
for(i=1;i<=g->nvertices;i++)
{
intree[i]=false;
distance[i]=MAXINT;
parent[i]=-1;
}
distance[start]=0;
v=start;
while(intree[v]==false)
{
intree[v]=true;//把结点v放入树中
for(i=0;i<g->degree[v];i++)//有几个相临结点
{
w=g->edges[v][i].v;//与结点v相邻的结点
weight=g->edges[v][i].weight;//到该结点的权重
if( distance[w]>(distance[v]+weight) )
{
distance[w]=distance[v]+weight;
parent[w]=v;
}
}
v=1;
dist=MAXINT;
for(i=2;i<=g->nvertices;i++)
{
if( (intree[i]==false) && (dist>distance[i]) )
{
dist=distance[i];
v=i;
}
}
}
}
void output(graph *g,int start,int end)
{
int delay;
int te;
int pass[MAXV];
int realpass[MAXV];
int i,j,k;
te=end;
delay=0;
i=0;
k=0;
realpass[k++]=start;
while(parent[end]!=start)
{
pass[i++]=parent[end];
end=parent[end];
}
for(j=i-1;j>=0;j--)
{
realpass[k++]=pass[j];
}
realpass[k]=te;
cout<<"Case "<<cas++<<": Path = ";
for(i=0;i<k;i++)
{
cout<<realpass[i]<<" ";
delay+=del[realpass[i]][realpass[i+1]];
}
cout<<realpass[i]<<"; "<<delay<<" second delay"<<endl;
}
int main()
{
graph g;
int n;
int i;
int start,end;
while(cin>>n&&n!=0)
{
init(&g,n);
cin>>start>>end;
dijkstra(&g,start);
output(&g,start,end);
}
return 0;
}
Can anyone tell me, why?
