2020牛客国庆七天乐day02 CHEAP DELIVERIES（最短路+状压dp）

admin管理员组

文章数量:1642741

链接：https://ac.nowcoder/acm/contest/7818/B
来源：牛客网
 

题目描述

Abu runs a delivery service where he deliver items from one city to another. As with any business, Abu wants to decrease his cost as much as possible. The further he travel, the more fuel he will use. 
In any particular day, Abu have k items to deliver. Each item needs to be delivered from a start city to a destination city. Each city is represented by an integer. Because of his business policies, he can only deliver one item at a time. However, he can deliver the items in any order that he wants, as long as he deliver all of them. So, everyday he starts at an item's start city and deliver the item to its destination city. Then, he goes to the next items's start city and deliver the item to the its destination city. And, he does this until he does not have any item left to deliver. 
From experimentation, Abu notices that the distance he travels change if he change the order of his delivery. He thought, he can save a lot of money if he knows the best delivery order. He knows that you are very good at solving this kind of problem. So he wants you to solve it for him. Given a list of cities, a list of roads between the cities (and the road's length), and a description of deliveries he must do, determine what is the minimum total travel distance, given that he execute his delivery in the most efficient order. 
Every road is bidirectional and there can be more than one road between two cities. Abu can use any road as many time as he wants.

输入描述:

The first line consists of two integer n, m, k (2 ≤n, m ≤ 104)(2 \leq n, m \leq 10^4)(2 ≤n, m ≤ 104), (1 ≤ k ≤ 18)(1 \leq k \leq 18)(1 ≤ k ≤ 18) which is the number of cities, the number of roads and the number of items respectively. 
The next m line each consist of 3 integers, uiu_iui​,viv_ivi​, lil_ili​ (1 ≤ ui, vi ≤ 104)(1 \leq u_i, v_i \leq 104)(1 ≤ ui​, vi​ ≤ 104), (1 ≤ li ≤ 106)(1 ≤ l_i ≤ 10^6)(1 ≤ li​ ≤ 106), which denotes that a road exists from city ui to vi with length li. 
The next k line each consist of 2 integers, fif_ifi​, did_idi​ (1 ≤ fi, di ≤ 104)(1 ≤ f_i, d_i ≤ 10^4)(1 ≤ fi​, di​ ≤ 104) which denotes that the ith item is from city fi and its destination is city did_idi​.

输出描述:

A single integer, which is the minimum total travel distance given that Abu deliver all items optimally, or -1 if its is impossible for him to deliver all items.

示例1

输入

复制5 5 3 1 2 1 2 3 2 3 4 3 4 5 4 5 2 4 2 3 1 2 5 3

5 5 3 
1 2 1 
2 3 2 
3 4 3 
4 5 4 
5 2 4 
2 3 
1 2 
5 3 
 

输出

复制12

12

说明

In the first example, Abu can start from city 5, and deliver the third item, so he move to city 3, travelling a total distance of 6 by going through city 2, then he goes to city 1, travelling a distance of 3 through city 2, and then he deliver the first item to city 2 and then deliver the second item to city 3. The total travel distance is 12.

示例2

输入

复制5 5 4 1 2 10 5 3 10 2 4 1 4 1 2 3 5 4 1 2 3 5 4 1 2 4

5 5 4 
1 2 10 
5 3 10 
2 4 1 
4 1 2 
3 5 4 
1 2 
3 5 
4 1 
2 4 

输出

复制-1

-1

说明

In the second example, city 1, 2 and 4 is disconnected from city 3 and 5, therefore it is impossible for Abu to deliver all item.

题意：求连续走过全部k条路线的最小花费 k<=18

思路：最短路+状压dp

 代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>

#define int long long
#define pll pair<int,int>

using namespace std;

const int maxn=1e4+5,inf=0x3f3f3f3f;

int e[maxn<<1],nex[maxn<<1],cost[maxn<<1],head[maxn],cnt;
int dis[20][20],dist[maxn],f[20][1<<20];
int n,m,k,s[20],t[20];
bool vis[maxn];

void add(int u,int v,int w)
{
    e[cnt]=v,cost[cnt]=w,nex[cnt]=head[u],head[u]=cnt++;
}

void bfs(int st)
{
    priority_queue<pll,vector<pll>,greater<pll>>heap;
    heap.push({0,st});
    dist[st]=0;
    while(heap.size()){
        pll t=heap.top();
        heap.pop();
        int u=t.second;
        if(vis[u]) continue;
        vis[u]=true;
        for(int i=head[u];~i;i=nex[i]){
            int v=e[i],len=cost[i];
            if(vis[v]) continue;
            if(dist[u]+len<dist[v]){
                dist[v]=dist[u]+len;
                heap.push({dist[v],v});
            }
        }
    }
}

signed main()
{
    memset(head,-1,sizeof head);
    cin>>n>>m>>k;
    while(m--){
        int u,v,w;
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,w);
    }
    for(int i=1;i<=k;i++) cin>>s[i]>>t[i];
    for(int i=1;i<=k;i++){
        for(int j=1;j<=n;j++) dist[j]=inf,vis[j]=false;
        bfs(t[i]);//得到从当前路线终点到其他各个点的最短路
        for(int j=1;j<=k;j++) dis[i][j]=dist[s[j]];//得到从当前路线i的终点到其他各个路线j的起点的最短路作为第i条路线到第j条路线的最短路
    }
    //dp:f[i][j]表示当前点为i且走过的路线状态为j(二进制为10分别表示走没走过那个数位的路线)
    for(int i=1;i<(1<<k);i++){
        for(int j=1;j<=k;j++) f[j][i]=inf;
    }
    for(int i=1;i<=k;i++) f[i][1<<i-1]=dis[i][i];
    for(int i=1;i<(1<<k);i++){
        for(int s=1;s<=k;s++){
            if(i&(1<<(s-1))){
                for(int t=1;t<=k;t++){
                    if(i&(1<<(t-1))) continue;
                    f[t][i|(1<<t-1)]=min(f[t][i|(1<<(t-1))],f[s][i]+dis[s][t]+dis[t][t]);
                }
            }
        }
    }
    int res=inf;
    for(int i=1;i<=k;i++) res=min(res,f[i][(1<<k)-1]);//枚举所有终点为i并走过所有点的最优解，取其中的极小值
    if(res>=inf) cout<<-1<<endl;
    else cout<<res<<endl;
    return 0;
}

本文标签： 国庆七天乐状压DPcheap