POJ3068："Shortest" pair of paths—

POJ3068："Shortest" pair of paths——题解

阅读量：6261 次

发布时间：2019-06-22

本文共 1185 字，大约阅读时间需要 3 分钟。

题目大意：

从0～n-1找到两条边和点都不相同（除了0和n-1外）的最小费用路径。

————————————————————————————

魔改版。

按照那题的思路并且把点拆成中间连一条容量为1的边即可。

切了切了。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long ll;const int INF=1e9;const int N=70;const int M=20100;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct node{ int nxt; int to; int w; int b;}edge[M];int head[N],cnt=-1;void add(int u,int v,int w,int b){ cnt++; edge[cnt].to=v; edge[cnt].w=w; edge[cnt].b=b; edge[cnt].nxt=head[u]; head[u]=cnt; return;}int dis[N];bool vis[N];inline bool spfa(int s,int t,int n){ deque
           
            q; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++)dis[i]=INF; dis[t]=0;q.push_back(t);vis[t]=1; while(!q.empty()){ int u=q.front(); q.pop_front();vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; int b=edge[i].b; if(edge[i^1].w&&dis[v]>dis[u]-b){ dis[v]=dis[u]-b; if(!vis[v]){ vis[v]=1; if(!q.empty()&&dis[v]