首页 > 代码库 > POJ 1511 Invitation Cards

POJ 1511 Invitation Cards

2024-07-15 09:05:59   219人阅读

题目来源：http://poj.org/problem?id=1511

　　题目很长，花了不少时间才理解题意，目的就是为了求出来回两次最小路径（即为本题的差旅费）之和，

第一次从CCS(1)出发到各个点路径最小，SPFA算法没得说，回来时终点是确定的都是CCS(1)，相当于把路

径反过来，即把有向图去反方向，又是从1出发到各个点路径最小，再用一个SPFA。注意ans要用long long

不然也WA，这个地方WA了好几次，虽然更改后AC了，但还是不明白，题目明明写了smaller than 1000000000,

真是无语。

 1 #include<stdio.h> 2 #include<string.h> 3 #define INF 0x3f3f3f3f 4 const int maxn=1000000+10; 5 int u[maxn],v[maxn],w[maxn],next[maxn],first[maxn],dist[maxn],que[maxn]; 6 bool inq[maxn]; 7 void add_edge(int a,int e) 8 { 9     next[e]=first[a];10     first[a]=e;11 }12 void spfa(void)13 {14     int head,tail;15     dist[1]=0;16     que[head=tail=0]=1;17     tail++;18     inq[1]=true;19     while(head!=tail){20         int a=que[head];21         head=(head+1)%maxn;22         inq[a]=false;23         for(int e=first[a];e!=-1;e=next[e]){24             if(dist[v[e]]>dist[a]+w[e]){25                 dist[v[e]]=dist[a]+w[e];26                 if(!inq[v[e]]){27                     inq[v[e]]=true;28                     que[tail]=v[e];29                     tail=(tail+1)%maxn;30                 }31             }32         }33     }34 }35 int main()36 {37     int t,q,p;38     scanf("%d",&t);39     while(t--){40         scanf("%d%d",&p,&q);41         memset(first,-1,sizeof(int)*(p+1));42         for(int e=1;e<=q;e++){43             scanf("%d%d%d",&u[e],&v[e],&w[e]);44             add_edge(u[e],e);45         }46         memset(dist,0x3f,sizeof(int)*(p+1));47         memset(inq,false,sizeof(bool)*(p+1));48         spfa();49         long long ans=0;50         for(int i=1;i<=p;i++)51             ans+=dist[i];52         memset(first,-1,sizeof(int)*(p+1));53         for(int e=1;e<=q;e++){54             int t=u[e];55             u[e]=v[e];56             v[e]=t;57             add_edge(u[e],e);58         }59         memset(dist,0x3f,sizeof(int)*(p+1));60         memset(inq,false,sizeof(bool)*(p+1));61         spfa();62         for(int i=1;i<=p;i++)63             ans+=dist[i];64         printf("%lld\n",ans);65     }66     return 0;67 }

 


联系
我们