"Shortest" pair of paths
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 1215 | Accepted: 491 |
Description
A chemical company has an unusual shortest path problem.
There are N depots (vertices) where chemicals can be stored. There are M individual shipping methods (edges) connecting pairs of depots. Each individual shipping method has a cost. In the usual problem, the company would need to find a way to route a single shipment from the first depot (0) to the last (N - 1). That's easy. The problem they have seems harder. They have to ship two chemicals from the first depot (0) to the last (N - 1). The chemicals are dangerous and cannot safely be placed together. The regulations say the company cannot use the same shipping method for both chemicals. Further, the company cannot place the two chemicals in same depot (for any length of time) without special storage handling --- available only at the first and last depots. To begin, they need to know if it's possible to ship both chemicals under these constraints. Next, they need to find the least cost of shipping both chemicals from first depot to the last depot. In brief, they need two completely separate paths (from the first depot to the last) where the overall cost of both is minimal.
Your program must simply determine the minimum cost or, if it's not possible, conclusively state that the shipment cannot be made.
There are N depots (vertices) where chemicals can be stored. There are M individual shipping methods (edges) connecting pairs of depots. Each individual shipping method has a cost. In the usual problem, the company would need to find a way to route a single shipment from the first depot (0) to the last (N - 1). That's easy. The problem they have seems harder. They have to ship two chemicals from the first depot (0) to the last (N - 1). The chemicals are dangerous and cannot safely be placed together. The regulations say the company cannot use the same shipping method for both chemicals. Further, the company cannot place the two chemicals in same depot (for any length of time) without special storage handling --- available only at the first and last depots. To begin, they need to know if it's possible to ship both chemicals under these constraints. Next, they need to find the least cost of shipping both chemicals from first depot to the last depot. In brief, they need two completely separate paths (from the first depot to the last) where the overall cost of both is minimal.
Your program must simply determine the minimum cost or, if it's not possible, conclusively state that the shipment cannot be made.
Input
The input will consist of multiple cases. The first line of each input will contain N and M where N is the number of depots and M is the number of individual shipping methods. You may assume that N is less than 64 and that M is less than 10000. The next M lines will contain three values, i, j, and v. Each line corresponds a single, unique shipping method. The values i and j are the indices of two depots, and v is the cost of getting from i to j. Note that these shipping methods are directed. If something can be shipped from i to j with cost 10, that says nothing about shipping from j to i. Also, there may be more than one way to ship between any pair of depots, and that may be important here.
A line containing two zeroes signals the end of data and should not be processed.
A line containing two zeroes signals the end of data and should not be processed.
Output
follow the output format of sample output.
Sample Input
2 1
0 1 20
2 3
0 1 20
0 1 20
1 0 10
4 6
0 1 22
1 3 11
0 2 14
2 3 26
0 3 43
0 3 58
0 0
Sample Output
Instance #1: Not possible
Instance #2: 40
Instance #3: 73
Source
m条有向边连接了n个仓库，每条边都有一定费用。
将两种危险品从0运到n-1，除了起点和终点外，危险品不能放在一起，也不能走相同的路径。
求最小的费用是多少。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
#include <set>
using namespace std;
#define MM(a,b) memset(a,b,sizeof(a))
typedef long long ll;
typedef unsigned long long ULL;
const int mod = 1000000007;
const double eps = 1e-10;
const int inf = 0x3f3f3f3f;
const int big=50000;
int max(int a,int b) {return a>b?a:b;};
int min(int a,int b) {return a<b?a:b;};
const int N = 70;
const int M=10000+100;
struct edge{
int to,cap,cost,rev;
};
vector<edge> G[1005];
int dist[1005],inq[1005],prev[1005],prel[1005];
int n,m,x,y,c;
void add_edge(int u,int v,int cost)
{
G[u].push_back(edge{v,1,cost,G[v].size()});
G[v].push_back(edge{u,0,-cost,G[u].size()-1});
}
int mincost(int s,int t,int f)
{
int ans=0;
while(f>0)
{
memset(dist,inf,sizeof(dist));
memset(inq,0,sizeof(inq));
dist[s]=0;
queue<int> q;
q.push(s);
inq[s]=1;
MM(prev,-1);
while(!q.empty())
{
int u=q.front();
q.pop();inq[u]=0;
for(int j=0;j<G[u].size();j++)
{
edge &e=G[u][j];
if(e.cap>0&&dist[e.to]>dist[u]+e.cost)
{
dist[e.to]=dist[u]+e.cost;
prev[e.to]=u;
prel[e.to]=j;
if(!inq[e.to])
{
q.push(e.to);
inq[e.to]=1;
}
}
}
}
for(int i=t;i>s;)
{
int f=prev[i];
if(f==-1) return -1;//不存在符合要求的路径则退出
int j=prel[i];
G[f][j].cap-=1;
G[i][G[f][j].rev].cap+=1;
ans+=G[f][j].cost;
i=prev[i];
}
f-=1;//因为每条边容量都为1
}
return ans;
}
int main()
{
int kk=0;
while(~scanf("%d %d",&n,&m)&&(n||m))
{
for(int i=0;i<n;i++) G[i].clear();
for(int i=1;i<=m;i++)
{
scanf("%d %d %d",&x,&y,&c);
add_edge(x,y,c);
}
int ans=mincost(0,n-1,2);
if(ans==-1) printf("Instance #%d: Not possible
",++kk);
else printf("Instance #%d: %d
",++kk,ans);
}
return 0;
}
分析：最小费用流模板题，直接套的模板，刚开始忘记清空数组被TLE了