Problem Address：http://acm.zjut.edu.cn/ShowProblem.aspx?ShowID=1566
一道Dijkstra的算法题。
第一次看了一遍觉得可以用Dijkstra，刚好快看到那里，所以之后花了点时间看了那个算法。
后来又看到，于是开始写。但是写着写着发现不行。因为还要求返回的路程。
于是又搁下。
今天再看到，发现只要求两次就可以实现。
思路：进行一次Dijkstra，算出开始结点到每个点的最短路径。然后把所有边反向，重新（还是从开始结点）计算一次Dijkstra，就可以求出任何一个结点到达开始结点的最短路径。只要把打酱油的地点的对应的两个路径相加，选出最小值即可。
这是第一次写Dijkstra，所以可能写的有点粗糙。而且还不会用优先队列，所以时间得不到好的优化。
以下贴代码：
#include <iostream>using namespace std;const int MAX = 100000;int map1[1005][1005],map2[1005][1005];int d1[1005],d2[1005];int shop[1005];bool visited[1005];int n,e,k;int min(int a, int b){ if (a<=b) return a; else return b;}void dijkstra(int v, int map[1005][1005], int d[1005]){ int i,ct,temp,temppoint; for (i=1; i<=n; i++) { visited[i] = false; } d[v] = 0; ct = n; while(ct) { temp = MAX; for (i=1; i<=n; i++) { if (!visited[i]) { if (temp>d[i]) { temp = d[i]; temppoint = i; } } } visited[temppoint] = true; ct--; for (i=1; i<=n; i++) { if (map[temppoint][i]<MAX) { d[i] = min(d[temppoint]+map[temppoint][i],d[i]); } } }}int main(){ int i,j,a,b,val,len; while(scanf("%d %d %d", &n, &e, &k)!=EOF) { for (i=1; i<=n; i++) { for (j=1; j<=n; j++) { map1[i][j] = MAX; map2[i][j] = MAX; } } for (i=0; i<e; i++) { scanf("%d %d %d", &a, &b, &val); if (val<map1[a][b]) { map1[a][b] = val; map2[b][a] = val; } } for (i=1; i<=n; i++) { d1[i] = MAX; d2[i] = MAX; } for (i=0; i<k; i++) { scanf("%d", &shop[i]); } dijkstra(1, map1, d1); dijkstra(1, map2, d2); len = MAX; for (i=0; i<k; i++) { len = min(len, d1[shop[i]]+d2[shop[i]]); } printf("%d/n", len); } return 0;}
