hdu2066一个人的旅行(多源点多汇点的最短路径问题)

／＊

　　　思路：多源点，多会点的最短路径！

　　　将最小号－１的节点但最源点，将最大号＋１的点当作汇点！

　　　将问题转变成从一个源点到一个汇点的最短路径的问题！

　　　开始忘记初始化ｖｅｃｔｏｒ了，哇了好多次．．．．坑爹啊

＊／

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<vector>

#define M 1100

#define INF 0x3f3f3f3f

using namespace std;

struct node{

   int v;

   int tt;

   node(){}

   node(int v, int tt){

      this->v=v;

      this->tt=tt;

   }

};

vector<node>v[M];

int d[M], vis[M];

int city[M];

int n;

int T, S, D;

void Dijkstra(){

   memset(d, 0x3f, sizeof(d));

   memset(vis, , sizeof(vis));

   d[]=;

   vis[]=;

   int root=;

   for(int j=; j<=n; ++j){

       int minLen=INF, p, len=v[root].size();

       for(int i=; i<len; ++i){

          int u=v[root][i].v;

          if(!vis[u] && d[u] > d[root] + v[root][i].tt)

              d[u] = d[root] + v[root][i].tt;

       }//将所有的与ｒｏｏｔ节点连接的节点的距离进行更新

       for(int i=; i<=n+; ++i)／／然后从０节点到所有的节点的最短的距离！

          if(!vis[i] && minLen>d[i]){

             p=i;

             minLen=d[i];

          }

       if(minLen==INF)

          return;

       root=p;

       vis[root]=;

   }

}

int main(){

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

          int a, b, t;

          n=-;

          while(S--){

             cin>>a>>b>>t;

             v[a].push_back(node(b, t));

             v[b].push_back(node(a, t));

             n=max(n, max(a,b));

          }

          while(T--){

             cin>>a;

             v[].push_back(node(a, ));

             v[a].push_back(node(, ));

             n=max(n,a);

          }

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

             cin>>city[i];

             n=max(n, city[i]);

          }

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

             v[n+].push_back(node(city[i],INF));

             v[city[i]].push_back(node(n+,));

          }

          Dijkstra();

          for(int i=; i<=n+; ++i)

             v[i].clear();

          cout<<d[n+]<<endl;

      }

   return ;

}