Input输入数据有多组，每组的第一行是公交车的总数N(0<=N<=10000)；
第二行有徐总的所在地start，他的目的地end；
接着有n行，每行有站名s，站名e，以及从s到e的时间整数t(0<t<100)(每个地名是一个长度不超过30的字符串)。
note：一组数据中地名数不会超过150个。
如果N==-1，表示输入结束。
Output如果徐总能到达目的地，输出最短的时间；否则，输出“-1”。
Sample Input
6 xiasha westlake xiasha station 60 xiasha ShoppingCenterofHangZhou 30 station westlake 20 ShoppingCenterofHangZhou supermarket 10 xiasha supermarket 50 supermarket westlake 10 -1
Sample Output
50 Hint: The best route is: xiasha->ShoppingCenterofHangZhou->supermarket->westlake
本题其实一点都不难，只要会最短路和一个STl中的map容器就可以了。。。
为啥要用map容器，我感觉用其他的肯定要麻烦，用map可以直接找到，不用很循环来找这个地区所对应的编号（编号？？什么编号。。。你不用编号来代替最短路的边是从谁向谁那怎么办
。。。）
最后要注意的就是就是如果起点和终点相同时就要输出0，要分开讨论（是按我的代码，我对起点和终点分别赋值编号为1、2，这样的话当起点终点相同时就错了）
除了这个我还运行时错误，最后把char改成string，输入改成cin就没有了。。。。
这道题要把我气炸。。。。
下面是代码：
1 #include<stdio.h> 2 #include<string.h> 3 #include<queue> 4 #include<iostream> 5 #include<map> 6 #include<algorithm> 7 using namespace std; 8 const int INF=0xffffff; 9 struct shudui1 10 { 11 int start,value; 12 bool operator < (const shudui1 q)const 13 { 14 return value>q.value; 15 } 16 } str1; 17 struct shudui2 18 { 19 int start,value; 20 } str2; 21 priority_queue<shudui1>r; 22 map<string,int>t; 23 vector<shudui2>w[10005]; 24 int d[10005],dis[10005],n; 25 void JK() 26 { 27 memset(dis,0,sizeof(dis)); 28 while(!r.empty()) 29 { 30 str1=r.top(); 31 r.pop(); 32 int x=str1.start; 33 if(dis[x]) continue; 34 dis[x]=1; 35 int len=w[x].size(); 36 for(int i=0; i<len; ++i) 37 { 38 str2=w[x][i]; 39 if(!dis[str2.start] && d[str2.start]>d[x]+str2.value) 40 { 41 // printf("**\n"); 42 str1.value=d[str2.start]=d[x]+str2.value; 43 str1.start=str2.start; 44 r.push(str1); 45 } 46 } 47 } 48 } 49 int main() 50 { 51 while(~scanf("%d",&n)) 52 { 53 if(n==-1) break; 54 int flag=0,z; 55 string ss1,ss2,s1,s2; 56 cin>>ss1>>ss2; 57 t[ss1]=++flag; 58 t[ss2]=++flag; 59 for(int i=1; i<=n; ++i) 60 { 61 int x,y; 62 cin>>s1>>s2>>z; 63 if(t[s1]) 64 { 65 x=t[s1]; 66 } 67 else 68 { 69 t[s1]=++flag; 70 x=flag; 71 } 72 if(t[s2]) 73 { 74 y=t[s2]; 75 } 76 else 77 { 78 t[s2]=++flag; 79 y=flag; 80 } 81 str2.start=y; 82 str2.value=z; 83 w[x].push_back(str2); 84 str2.start=x; 85 w[y].push_back(str2); 86 } 87 if(ss1!=ss2) 88 { 89 str1.start=1; 90 str1.value=0; 91 for(int i=1; i<=150; ++i) 92 d[i]=INF; 93 d[1]=0; 94 r.push(str1); 95 JK(); 96 if(d[2]==INF) printf("-1\n"); 97 else printf("%d\n",d[2]); 98 } 99 else printf("0\n"); 100 for(int i=1; i<=n; ++i) 101 w[i].clear(); 102 t.clear(); 103 } 104 return 0; 105 }
InputFirst line contains two integers stand for N and M.
Then N lines follows, every line has M characters. "." stands for road, "a" stands for Angel, and "r" stands for each of Angel‘s friend.
Process to the end of the file.
OutputFor each test case, your program should output a single integer, standing for the minimal time needed. If such a number does no exist, you should output a line containing "Poor ANGEL has to stay in the prison all his life."
Sample Input
7 8 #.#####. #.a#..r. #..#x... ..#..#.# #...##.. .#...... ........
Sample Output
13
题意：
就是我们要从r到a，只有“#”不可以走，其他都可以，但是过x的时候要注意，过x要先把x这个眼给打了，才能过去，也就是过这个点需要时间比平常多一
这道题我想到了三种方法，但是有一种错了
先说对的：
一、
用优先队列
就是bfs从a走到r，因为r可能有多个，所以不能从r走，然后就是走到x的时候要把时间多加一，然后用优先队列来对时间从小到大排序，这个样子不就满足题意了嘛，
只要我们走到r的位置，就直接跳出来
二、
普通BFS
我们走到x的前一个位值，就先把他杀死再进去，具体代码实现就是，之让这个点的时间加一，但是他的位置不变，在地图上面要把这一个点的值改为“.”
错的方法：
普通BFS
但是一直在迷宫里走，遇到x就加二，，一旦遇到r要记录这个时间，不要直接输出，最后走完迷宫再输出
错误地方：题目上面说是把守卫打死，那就是说x再经过一次之后，这个地方就没有守卫了。。。。。
代码如下：
优先队列的
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <queue> 5 using namespace std; 6 7 int n, m; 8 char map[205][205]; 9 int sx, sy; 10 bool flag; 11 struct node { 12 int x, y, step; 13 bool operator <(const node & t) const 14 { 15 return step>t.step; 16 } 17 }; 18 int dx[]= {-1,0,0,1}; 19 int dy[]= {0,-1,1,0}; 20 21 void bfs() { 22 node now, tmp; 23 int i,xx,yy; 24 priority_queue<node> q; 25 now.x = sx, now.y = sy, now.step = 0; 26 map[sx][sy] = ‘#‘; 27 q.push(now); 28 while(!q.empty()) { 29 now = q.top(); 30 q.pop(); 31 // cout<<now.x<<" "<<now.y<<" "<<now.step<<endl; 32 for(i=0; i<4; i++) { 33 xx = now.x +dx[i]; 34 yy = now.y +dy[i]; 35 if(xx<0||xx>=n||yy<0||yy>=m||map[xx][yy]==‘#‘) continue; 36 if(map[xx][yy]==‘r‘) { 37 cout<<now.step+1<<endl; 38 flag = true; 39 return ; 40 } 41 if(map[xx][yy]==‘x‘) { 42 tmp.x =xx, tmp.y = yy, tmp.step = now.step+2; 43 q.push(tmp); 44 } else { 45 tmp.x =xx, tmp.y = yy, tmp.step = now.step+1; 46 q.push(tmp); 47 } 48 map[xx][yy] = ‘#‘; 49 } 50 } 51 } 52 53 int main() { 54 int i, j; 55 while(~scanf("%d%d",&n,&m)) { 56 for(i=0; i<n; i++) 57 for(j=0; j<m; j++) { 58 cin>>map[i][j]; 59 if(map[i][j]==‘a‘) 60 sx=i,sy=j; 61 } 62 flag = false; 63 bfs(); 64 if(!flag) printf("Poor ANGEL has to stay in the prison all his life.\n"); 65 } 66 return 0; 67 }
F - JDG HDU - 2112 （最短路）&& E - IGNB HDU - 1242 （dfs）
原文：https://www.cnblogs.com/kongbursi-2292702937/p/10695462.html
