题意：给定一张图，求从1到n+1的最长距离。
bfs即可，没什么技巧。
View Code
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 #include<algorithm> 5 #include<queue> 6 #include<stack> 7 using namespace std; 8 const int maxn = 105; 9 const int maxm = 10000; 10 const int inf = 99999999; 11 int cnt,head[ maxn ]; 12 struct node{ 13 int u,val,next; 14 }edge[ maxm ]; 15 int n,m; 16 int val[ maxn ]; 17 int dis[ maxn ],vis[ maxn ],path[ maxn ]; 18 19 void init(){ 20 cnt=0; 21 memset( head,-1,sizeof( head )); 22 } 23 24 void addedge( int a,int b,int c ){ 25 edge[ cnt ].u=b; 26 edge[ cnt ].val=c; 27 edge[ cnt ].next=head[ a ]; 28 head[ a ]=cnt++; 29 } 30 31 void bfs(){ 32 for( int i=1;i<=n+1;i++ ){ 33 vis[i]=0; 34 dis[i]=-inf; 35 path[i]=-1; 36 } 37 queue<int>q; 38 while( !q.empty() ) 39 q.pop(); 40 q.push( 1 ); 41 vis[1]=1; 42 dis[1]=0; 43 while( !q.empty() ){ 44 int now=q.front(); 45 q.pop(); 46 vis[ now ]=0; 47 for( int i=head[ now ];i!=-1;i=edge[ i ].next ){ 48 int next=edge[i].u; 49 if( dis[next]<dis[now]+val[next] ){ 50 dis[next]=dis[now]+val[next]; 51 path[next]=now; 52 if( vis[next]==0 ){ 53 vis[next]=1; 54 q.push(next); 55 } 56 } 57 } 58 } 59 } 60 void output(){ 61 printf("points : %d\n",dis[n+1]); 62 stack<int>s; 63 for( int i=n+1;i!=-1;i=path[i] ){ 64 s.push( i ); 65 } 66 printf("circuit : "); 67 printf("%d",s.top()); 68 s.pop(); 69 while( !s.empty() ){ 70 if( s.top()==(n+1) ) 71 printf("->%d",1); 72 else 73 printf("->%d",s.top()); 74 s.pop(); 75 } 76 printf("\n"); 77 } 78 int main(){ 79 int T; 80 scanf("%d",&T); 81 for( int ca=1;ca<=T;ca++ ){ 82 if( ca!=1 ) 83 printf("\n"); 84 scanf("%d",&n); 85 for( int i=1;i<=n;i++ ) 86 scanf("%d",&val[ i ]); 87 val[n+1]=0; 88 scanf("%d",&m); 89 int a,b; 90 init(); 91 while( m-- ){ 92 scanf("%d%d",&a,&b); 93 if( a<b ){ 94 addedge( a,b,0 ); 95 } 96 else if( a>b ){ 97 addedge( b,a,0 ); 98 } 99 } 100 bfs(); 101 printf("CASE %d#\n",ca); 102 //printf("%d\n",dis[n+1]); 103 output(); 104 } 105 return 0; 106 }