| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 2808 | Accepted: 860 |
Description
Input
Output
Sample Input
6 0 3 4 -1 -1 -1 -1 0 4 5 -1 -1 2 3 0 -1 -1 2 8 9 5 0 1 -1 7 2 1 -1 0 -1 5 -1 4 5 4 0 2 4 5 6 In the above input the last line indicates that "2" is the location of the fire and "4", "5" and "6" are the intersections where fire stations are located.
Sample Output
Org Dest Time Path 5 2 2 5 2 4 2 3 4 5 2 6 2 6 6 5 2
题目链接：http://poj.org/problem?id=1122
题意：有n个交叉路口，N×N的矩阵，edge[i][j]表示第i个交叉路口到底j个交叉路口的时间（注意：edge[i][j]不一定等于edge[j][j]）输入一个着火点，接着输入消防站。输出消防站到着火点的时间，具体格式看样例。
思路：终点固定，起点不唯一。把图逆向存储，那么起点就固定了，终点就不唯一。输出最短路径，用Dijkstra算法（这题的输入输出格式需要注意一下）
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define INF 10000000 int n,num,fire; int edge[50][50]; int sign[50],near[50]; int loc[50]; struct node { int t,p,gg; } ans[50]; int cmp(node a,node b) { return a.t<b.t; } void Init() { cin>>n; int i,j; for(i=1; i<=n; i++) { ans[i].t=INF; ans[i].gg=0; sign[i]=0; } for(j=1; j<=n; j++) for(i=1; i<=n; i++) scanf("%d",&edge[i][j]); scanf("%d",&fire); } void Dijkstra(int v) { int i,j; ans[v].t=0; for(i=0; i<n; i++) { sign[v]=1; int Min=INF,flag; for(j=1; j<=n; j++) { if(edge[v][j]>=0&&ans[v].t+edge[v][j]<ans[j].t) { ans[j].t=ans[v].t+edge[v][j]; near[j]=v; } if(sign[j]==0&&ans[j].t<Min) { Min=ans[j].t; flag=j; } } v=flag; } } int main() { int i,j; Init(); Dijkstra(fire); int pp; while(scanf("%d",&pp)!=EOF) { ans[pp].gg=1; } for(i=1; i<=n; i++) ans[i].p=i; sort(ans,ans+n+1,cmp); cout<<"Org\tDest\tTime\tPath"<<endl; for(i=1; i<=n; i++) { if(ans[i].gg==1) { printf("%d\t%d\t%d\t",ans[i].p,fire,ans[i].t); int flag=ans[i].p; while(flag!=fire) { cout<<flag<<"\t"; flag=near[flag]; } cout<<fire<<endl; } } return 0; }
原文：http://www.cnblogs.com/GeekZRF/p/5419518.html
