POJ 2387

  1 #include<iostream>
  2 #include<stdio.h>
  3 #define MAXN 1005
  4 #define inf 10000000
  5 using namespace std;
  6 int _m[MAXN][MAXN];
  7 int dij[MAXN];
  8 void Dijkstra(int m,int s);
  9 int main()
 10 {
 11     //freopen("acm.acm","r",stdin);
 12     int t;
 13     int n;
 14     int i;
 15     int j;
 16     int u;
 17     int v;
 18     int value;
 19     cin>>t>>n;
 20     for(i = 0; i < MAXN; ++ i)
 21     {
 22         for(j = 0; j < MAXN; ++ j)
 23         {
 24             _m[i][j] = inf;
 25     //        _m[j][i] = inf;
 26         }
 27     }
 28     for(i = 0; i < t; ++ i)
 29     {
 30         cin>>u>>v>>value;
 31         -- u;
 32         -- v;
 33         if(_m[u][v] > value)
 34         {
 35             _m[u][v] = value;
 36             _m[v][u] = value;
 37         }
 38     }
 39     //cout<<">>>>>>>>>"<<endl;
 40     Dijkstra(n,n-1);
 41 //    for(i = 0; i < n; ++ i)
 42 //    {
 43         cout<<dij[0]<<endl;
 44 //    }
 45 }
 46 
 47 void Dijkstra(int m,int s)
 48 {
 49     int i;
 50     int j;
 51     int min;
 52     int * mark = new int[m];                    
 53     memset(mark,0,m*sizeof(int));
 54     memset(dij,-1,sizeof(dij));
 55     dij[s] = 0;                                
 56     mark[s] = 1;                        
 57     int x;
 58     int k;
 59     min = -1;                                
 60     for(i = 0; i < m; ++ i)
 61     {
 62         if(_m[s][i] != inf)
 63             dij[i] = _m[s][i];
 64     //    cout<<"090900999  "<<dij[i]<<endl;
 65     }
 66     //for(i = 0; i < m; ++ i)
 67 //        {
 68 //            cout<<" dij "<<dij[i];
 69     //    }
 70     for(k = 0; k < m; k++)                    
 71     {                
 72         min = -1;                            
 73         for(j = 0; j < m; j++)                
 74         {
 75             if(mark[j] == 0 && dij[j] > 0)
 76             {
 77                 if(dij[j] < min || min < 0)
 78                 {
 79                     min = dij[j];            
 80                     x = j;
 81                 }
 82             }
 83         }
 84         
 85         mark[x] = 1;
 86     //    cout<<dij[x]<<"min"<<endl;
 87         
 88     //    cout<<"00000000000000"<<endl;
 89         for(i = 0; i < m; ++ i)                        
 90         {    
 91             if(mark[i] == 0 && _m[x][i] != inf)
 92             {
 93             
 94                 if(dij[i] < 0 || dij[x] + _m[x][i] < dij[i])
 95                 {
 96                     dij[i] = dij[x] + _m[x][i];
 97                 }
 98             }
 99         }
100     }
101     delete []mark;
102 }