hdu--1224--spfa||dp

  1 #include <iostream>
  2 #include <cstring>
  3 #include <queue>
  4 #include <stack>
  5 using namespace std;
  6 
  7 int n;
  8 const int size = 110;
  9 struct graph
 10 {
 11     int num;
 12     int next[size-10];
 13 }node[size];
 14 int val[size];
 15 int sum[size];
 16 int path[size];
 17 bool vis[size];
 18 queue<int>q;
 19 stack<int>s;
 20 
 21 void init( )
 22 {
 23     while( !q.empty() )
 24         q.pop();
 25     for( int i = 0 ; i<size-5 ; i++ )
 26         node[i].num = 0;
 27     memset( vis , false , sizeof(vis) );
 28     memset( sum , 0 , sizeof(sum) );
 29     memset( path , -1 , sizeof(path) );
 30 }
 31 
 32 void spfa( )
 33 {
 34     int now , point;
 35     q.push(1);
 36     vis[1] = true;
 37     while( !q.empty() )
 38     {
 39         now = q.front();
 40         q.pop();
 41         for( int i = 0 ; i<node[now].num ; i++ )
 42         {
 43             point = node[now].next[i];
 44             if( sum[now] + val[point] >= sum[point] )
 45             {
 46                 sum[point] = sum[now] + val[point];
 47                 path[point] = now;
 48                 if( !vis[point] )
 49                 {
 50                     vis[point] = true;
 51                     q.push(point);
 52                 }
 53             }
 54         }
 55         vis[now] = false;
 56     }
 57 }
 58 
 59 void output( )
 60 {
 61     s.push( n+1 );
 62     for( int i = path[n+1] ; i!=-1 ; i=path[i] )
 63     {
 64         s.push( i );
 65     }
 66     while( !s.empty( ) )
 67     {
 68         if( s.top() == n+1 )
 69         {
 70             cout << 1;
 71         }
 72         else
 73         {
 74             cout << s.top( ) << "->";
 75         }
 76         s.pop();
 77     }
 78     cout << endl;
 79 }
 80 
 81 int main()
 82 {
 83     int t , m , cnt , x , y , num;
 84     while( cin >> t )
 85     {
 86         cnt = 1;
 87         for( int k = 1 ; k<=t ; k++ )
 88         {
 89             init();
 90             cin >> n; // n+1个结点
 91             for( int i = 1 ; i<=n ; i++ )
 92             {
 93                 cin >> val[i];
 94             }
 95             val[n+1] = 0;
 96             cin >> m;
 97             while( m-- ) // m对关系
 98             {
 99                 cin >> x >> y;
100                 num = node[x].num;
101                 node[x].next[ node[x].num++ ] = y;
102             }
103             spfa();
104             cout << "CASE " << cnt++ << "#" << endl;
105             cout << "points " << ": " << sum[n+1] << endl;
106             cout << "circuit : ";
107             output( );
108             if(k<t)
109                 cout << endl;
110         }
111     }
112     return 0;
113 }