#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include <iostream>
using namespace std;
const int MAX=25;
const int INF=1<<27;
//graph info.
int n;
int w[MAX][MAX];
//dij info.
int s;
int dist[MAX];
int p[MAX];
bool flag[MAX];
int dest[MAX];//消防站所在顶点
void reversal(){
int i,j;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
if(w[i][j]==-1) w[i][j]=INF;
}
}
for(i=1;i<=n;i++){
for(j=1;j<i;j++){
w[i][j]^=w[j][i]^=w[i][j]^=w[j][i];
}
}
}
void dij(){
int i;
for(i=1;i<=n;i++){ //注:这里最好不要初始化为INF和i/-1,否则出错或者不好写,待总结
dist[i]=w[s][i];
p[i]=s;
}
memset(flag,false,sizeof(flag));
flag[s]=true;
int time=n-1;
while(time--){
//找本次加入S的点cur
int cur;
int minValue=INF;
for(i=1;i<=n;i++){
if(flag[i]==false && dist[i]<minValue){
minValue=dist[i];
cur=i;
}
}
flag[cur]=true;
//更新cur的邻接点
for(i=1;i<=n;i++){
if(flag[i]==false && w[cur][i]<INF && dist[cur]+w[cur][i]<dist[i]){
p[i]=cur;
dist[i]=dist[cur]+w[cur][i];
}
}
}
}
//s: 目的点
void printPath(int i){
printf("%d\t",i);
if(i!=s)
printPath(p[i]);
}
//dest[i]中节点按照dist[dest[i]]升序排列
bool compare(int a,int b){
return dist[a]<dist[b];
}
int main(){
//输入
scanf("%d",&n);
int i,j;
int tempInt=-1;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
scanf("%d",&w[i][j]);
}
}
scanf("%d",&s);
int pos=1;
while(scanf("%d",&dest[pos])){ //???通用方式
pos++;
char ch=getchar();
if(ch=='\n')
break;
}
pos--;
//dij
reversal();
dij();
//输出
printf("%s\t%s\t%s\t%s\n","Org","Dest","Time","Path");
sort(dest+1,dest+pos+1,compare);
for(i=1;i<=pos;i++){
printf("%d\t%d\t",dest[i],s);
printf("%d\t",dist[dest[i]]);
printPath(dest[i]);
printf("\n");
}
system("pause");
return 0;
}
分享到:
相关推荐
NULL 博文链接:https://200830740306.iteye.com/blog/603493
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 2763 程序 线段树 LCA 2000MS AC
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
NULL 博文链接:https://128kj.iteye.com/blog/1705139
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
POJ题解 个人写法 线段树每个人都不一样
NULL 博文链接:https://128kj.iteye.com/blog/1704752
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
先利用prim算法求出最小生成树,然后通过往MST里加边来判断新生成的最小生成树是否具有最小的权值,POJ上The Unique MST(1679)题是要求判断最小生成树是否唯一,此题其实根本不用这样做,但是为了练习球次小生成树...
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码