Description
吉姆雷诺的游骑兵们想要摧毁蒙斯克帝国的一个要塞，但是游骑兵们需要找到一条最快的路径来抵达要塞并摧毁。这样的突袭是蒙斯克绝对想不到的。现在游骑兵找来了一张地图，地图上标出了所有可以通行的路，游骑兵标出了每条路的长度和这条路上允许的最快速度。已知每单位距离消耗的油是一定的，吉姆雷诺想知道如果选择最快的路径到达要塞需要准备多少石油。游骑兵们的出发地点是一个叫carle的地方，要塞所在的地方叫mensker
Input
本题有多组测试数据，一直处理到文件结束。对于每组数据，先输入三个整数n、m和k表示地点的个数（n不会超过1000）和每两个地点间的公路数目和每个单位距离消耗的油量，接下来有m行数据，输入方式如下：
地点1 地点2 公路长度 允许最大速度
Output
输出吉姆雷诺需要准备的单程石油数量并换行
Sample Input
4 3 1
carle temp 100 50
temp mensker 100 10
carle somewhere 100 100
Sample Output
200
参考代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
#define INF 0x3f3f3f
using namespace std;
double Time[1005][1005];
double Speed[1005][1005];
int vis[1005];
double disT[1005];
double disS[1005];
int n, m, k;
int startPoint;
int endPoint;
void Dijkstra(int st, int ed)
{for (int i = 1;i <= n;i++){vis[i] = 0;}for (int i = 1;i <= n;i++){disT[i] = Time[st][i];disS[i] = Speed[st][i] * Time[st][i];}vis[st] = 1;disT[st] = 0;disS[st] = 0;int u;for (int i = 1;i <= n-1;i++){double min = INF;for (int j = 1;j <= n;j++){if (!vis[j] && min > disT[j]){u = j;min = disT[j];}}vis[u] = 1;for (int l = 1;l <= n;l++){if (Time[u][l] != INF){if (disT[l] > disT[u] + Time[u][l]){disT[l] = disT[u] + Time[u][l];disS[l] = disS[u] + Time[u][l] * Speed[u][l];}}}}
}
int main()
{while (cin>>n>>m>>k){for (int i = 1;i <= n;i++){for (int j = 1;j <= n;j++){if (i == j){Time[i][j] = 0;}else{Time[i][j] = INF;}Speed[i][j] = 0;}}for (int i = 1;i <= n;i++){disT[i] = INF;disS[i] = INF;}int id = 1;map<string, int>s;for (int i = 1;i <= m;i++){string st,ed;double len,v;cin >> st >> ed >> len >> v;if (!s[st])s[st] = id++;if (!s[ed])s[ed] = id++;if (st == "carle")startPoint = s[st];if (ed == "mensker")endPoint = s[ed];Time[s[st]][s[ed]] = len / v;Speed[s[st]][s[ed]] = v;}Dijkstra(startPoint, endPoint);printf("%.0lf\n", disS[endPoint]*k);}
}