Choose the best route

 hdu 2680：http://acm.hdu.edu.cn/showproblem.php?pid=2680

这道题值得一提的两点：
在图论中注意重边问题是必须的，有向无向也是同等重要的，如这道题 from station p to station q说的就很清楚是有向图
此题如果暴力求解把每个临近的车站都作为源点走一遍，就会超时。此时的做法是
在与临近的车站加上一个0，并使其的距离为零，这样就可以转化成单源点的问题

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxint=1008;
int dist[maxint];
int c[maxint][maxint];
int s[maxint];
int qu;
int n,m;
void solve(int v){
    for(int i=1;i<=n;i++){
        dist[i]=c[v][i];
        s[i]=0;
        }
    s[v]=1;
    dist[v]=0;
    for(int i=1;i<=n;i++){
        int min=100000000;
        int k;
        for(int j=1;j<=n;j++){
                if(!s[j]&&dist[j]<min)

       {     min=dist[j];
               k=j;

   }
    }
        if(min==100000000)
        break;
        s[k]=1;
        for(int j=1;j<=n;j++)
        {
             if(s[j]==0&&dist[j]>dist[k]+c[k][j])
               dist[j]=dist[k]+c[k][j];
        }

         }
}
 int main(){
     while(scanf("%d %d %d",&n,&m,&qu)!=EOF){
         for(int i=0;i<1008;i++){
             for(int j=0;j<1008;j++){
                 c[i][j]=100000000;
             }
         }
         int a,b,w;
         for(int i=1;i<=m;i++){
             scanf("%d%d%d",&a,&b,&w);
             if(w<c[a][b]){
                 c[a][b]=w;
             }
         }//无向图，并且去重
         int e;
         scanf("%d",&e);
         int f;
         for(int i=0;i<e;i++){
             scanf("%d",&f);
             c[0][f]=0;
             }
             solve(0);
         if(dist[qu]==100000000)
         printf("-1
");
         else
         printf("%d
",dist[qu]);


     }

 }