说走就走的旅行-题解（C++代码）

解题思路:
通过迪杰斯特拉算法计算两点之间的最短路径
注意事项:
需计算城市数量，否则会超时
参考代码:

#include<iostream>

#include<algorithm>

using namespace std;

int main()

{

    int T,S,D;

    int a,b,time;

    while(cin>>T>>S>>D)

    {

        int map[1001][1001];    //城市间距离

        int index[1001];        //记录城市

        int total=1;            //城市数量(有重复)

        for(int i=1;i<=1000;i++)        //初始化数组

        {

            map[i][i]=0;

            for(int j=i+1;j<=1000;j++)

            {

                map[i][j]=999;

                map[j][i]=999;

            }

        }

        for(int i=1;i<=T;i++)    //数组预处理

        {

            cin>>a>>b>>time;

            map[a][b]=time;

            map[b][a]=time;

            index[total++]=a;

            index[total++]=b;

        }

        for(int k=1;k<=total-1;k++)     //迪杰斯特拉算法

        for(int i=1;i<=1000;i++)

        for(int j=i+1;j<=1000;j++)

        {

            map[i][j]=min(map[i][j],map[i][index[k]]+map[index[k]][j]);

            map[j][i]=map[i][j];

        }

        int s[1001],d[1001];

        for(int i=1;i<=S;i++)

            cin>>s[i];

        for(int i=1;i<=D;i++)

            cin>>d[i];

        int minTime=999;

        for(int i=1;i<=S;i++)     //依次查看所有起点到终点的时间，选择最小值

        for(int j=1;j<=D;j++)

        {

            minTime=min(minTime,map[s[i]][d[i]]);

        }

        cout<<minTime<<endl;

    }

    return 0;

}