Description:
The best friends Mr. Li and Mr. Liu are touring in beautiful country M.
M has n cities and m two-way roads in total. Each road connects two cities with fixed length.We assume that the cost of car traveling on the road is only related to the length of road,the longer road the more money to pay.
Now,both Mr. Li and Mr. Liu are in the city C,they have chosen to travel separately by the next time.
Mr. Li chooses city A with beautiful scenery to be next place, Mr. Liu goes to city B with ancient temples.
You are their friend with clever minds,just tell them how to arrive the target places make total costs of them minimum
Input:
The input file contains sevearl test cases.The first line of each case are two positive integers n,and m(3<=n<=5000, 1<=m<=10000). The cities are named from 1 to n.Three positive integers C, A, B are follwing.Then,m lines are given,each line contains three integers i,j and k,indicating one road between i and j is exists,and should pay cost k by the car.
Process to the end of file.
Output:
For each test case, first print a line saying "Scenario #p", where p is the number of the test case.Then,if both Mr. Li and Mr. Liu can manage to arrive their cities,output the minimum cost they will spend,otherwise output "Can not reah!", in one line.Print a blank line after each test case, even after the last one.
Sample Input:
4 5
1 3 4
1 2 100
1 3 200
1 4 300
2 3 50
2 4 100
4 6
1 3 4
1 2 100
1 3 200
1 4 300
2 3 50
2 4 100
3 4 50
Sample Output:
Scenario #1
250
Scenario #2
200
思路：
恩，，，大概意思说就是两个人都从C地出发，分别到达A，B两地，当两人共同走的路只用给一次车费，求最小花费···
其实想通之后觉得很好理解哒，，，就是在所有点中找到一个点，让它到A，B，C三个点的花费和最小，，，
然后怎么做捏，，，其实也很简单嘛，，，
算到两个点之间的最短路的时候，调用一次，那现在有三个点，调用三次就好啦，然后分别用lowa,lowb,lowc来记录，最后求最小的和就阔以咯···
代码：
#include#include #include using namespace std; #define INF 0x1f1f1f1f //定义的优先队列 struct str{ int num; int cost; str(int n,int c):num(n),cost(c){} str(){} friend bool operator <(str s1,str s2){ return s1.cost>s2.cost; }//嘛嘛，，，其实一直觉得这里是很奇怪的，像这样子的友元函数实现的功能是从小到大排序···所以就记着函数体里面是“>”咯 }; struct Arc{ int next_arc; int point; int cost; }; Arc arc[20005]; int head[5005]; bool fl[5005]; int lowa[5005]; int lowb[5005]; int lowc[5005]; int c,a,b; //这个函数主要是分别求出a,b,c到每一个它所能到达的点的最短距离 void dij(int src,int n,int *low){ //src 表示的分别是a,b,c点，，， memset(fl,0,sizeof(fl)); priority_queue q; //好吧，，，又是，第一次自己写结构体来定义优先队列； q.push(str(src,0));//加入源点a/b/c int kk=0; while(kk