poj 3767 I Wanna Go Home （有限制的最短路）

  1 #include<stdio.h>
  2 #include<iostream>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cmath>
  6 #include<queue>
  7 #include<set>
  8 #include<map>
  9 #define Min(a,b)  a>b?b:a
 10 #define Max(a,b)  a>b?a:b
 11 #define CL(a,num)  memset(a,num,sizeof(a));
 12 #define inf 9999999
 13 #define maxn 1030
 14 #define eps  1e-6
 15 using namespace std;
 16 int n,m;
 17 int mat[maxn][maxn],vis[maxn],pre[maxn],f[maxn],dis[maxn];
 18 void init()
 19 {
 20     for(int i=0; i<=n;i++)
 21     {
 22         for(int j=0;j<=n;j++)
 23             mat[i][j]=inf;
 24     }
 25 }
 26 void dij()
 27 {
 28     int i,j,k;
 29 
 30     for(i=0;i<=n;i++)
 31     {
 32         dis[i]=inf;
 33         vis[i]=0;
 34         pre[i]=0;
 35     }
 36     dis[1]=0;
 37     pre[1]=1;
 38     for(i=0;i<n;i++)
 39     {
 40         int min=inf;
 41         for(j=1;j<=n;j++)
 42         {
 43             if(!vis[j]&&dis[j]<min)
 44             {
 45                 min=dis[j];
 46                 k=j;
 47             }
 48         }
 49         vis[k]=1;
 50 
 51         for(j=1;j<=n;j++)
 52         {
 53 
 54 
 55 
 56 
 57             if(!vis[j]&mat[k][j]!=inf&&dis[j]>dis[k]+mat[k][j])
 58             {
 59 
 60 
 61 
 62                 dis[j]=dis[k]+mat[k][j];
 63 
 64             }
 65         }
 66 
 67     }
 68 }
 69 int main()
 70 {
 71     int i,x,y,z,a,j;
 72     while(scanf("%d",&n),n)
 73     {
 74         scanf("%d",&m);
 75         init();
 76         for(i=1;i<=m;i++)
 77         {
 78             scanf("%d%d%d",&x,&y,&z);
 79             mat[x][y]=mat[y][x]=z;
 80         }
 81         for(i=1;i<=n;i++)
 82         {
 83           scanf("%d",&f[i]);
 84 
 85         }
 86         for(i=1;i<=n;i++)
 87         {
 88             for(j=1;j<=n;j++)
 89             {
 90                 if(f[i]!=f[j])
 91                 {
 92                     if(f[i]==1&&f[j]==2)
 93                         mat[j][i]=inf;
 94                     else
 95                        if(f[j]==1&&f[i]==2)
 96                         mat[i][j]=inf;
 97                 }
 98             }
 99         }
100         dij();
101         if(dis[2]!=inf)printf("%d\n",dis[2]);
102         else printf("-1\n");
103     }
104 
105 }