UVA 10806 Dijkstra, Dijkstra.-白红宇

UVA 10806 Dijkstra, Dijkstra.

阅读量：6540 次

发布时间：2019-06-24

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

题意：

　　从起点走到终点，然后从终点走到起点，其中不能同时走过相同的一条边，问你最小路径长度。先输入终点n，起点为1，接下来输入m，代表有m条边。每条边由起点，终点，长度组成。　　

分析：

　　求最小长度，还限定了每条路只能一次，所以可以用网络流来接。长度就是边费用，每条边的流量为1，这样实现了每条边只能走一次。从起点走到终点再从终点走到起点，相当于在起点前连一个外起点，流量为2,。

代码：

#include 
    
     #include 
     
      #include 
      
        #include 
       
         #include 
        
          #include 
         
           using namespace std; const int maxn=110; const int INF=1e9; int n,m,s,t; int inq[maxn]; int d[maxn],p[maxn],a[maxn]; int flow,cost; struct Edge { int from,to,cap,flow,cost; }; vector
          
           edges; vector
           
            G[maxn]; void init() { flow=cost=s=0; t=n; for(int i=0;i

q; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); inq[u]=0; for(int i=0;i

e.flow&&d[e.to

转载于:https://www.cnblogs.com/137033036-wjl/p/5761670.html

你可能感兴趣的文章