Skip to content

14098: 【原4098】Run

题目

题目描述

author: Lmxyy 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4098

Description

啸啸喜欢参加定向越野比赛。比赛赛场是一个有\(N\)个点,\(M\)条边的图。比赛的起点为\(1\)号节点,终点为\(N\)号节点。在\(2 \sim N-1\)号节点中还有\(K\)个必经点,在这些必经点上有专人派发属于该点的特有flag。选手只有集齐所有\(K\)个flag,同时冲过终点线才算结束比赛。用时最短的选手将获得比赛的冠军。啸啸是个专业的选手,他在赛前就已经拿到了比赛的地图,他想知道他要怎样才能跑最短的路完成比赛?

Input Format

第一行三个整数\(N,M,K\),如题意。

第二行\(K\)个不同的整数\(A_i\),表示第\(i\)个关键点的编号。

接下来\(M\)行,每行三个数\(u_i,v_i,w_i\),表示\(u_i\)节点到\(v_i\)节点连接了一条长度为\(w_i\) 的双向边。

Output Format

输出一行,表示啸啸最少要跑多少路才能完成比赛。

若啸啸怎么都无法完成比赛(即无法收集所有的flag或者无法到达终点),输出\(-1\)。

Sample Input

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

Sample Output

5

Data Range

| 数据编号 | 数据特征 | | :------: | :----------------------------------------------------------: | | 1 | \(N \le 5\),\(M \le 10\),\(K = 0\),\(w_i = 1\) | | 2 | \(N \le 100\),\(M \le 200\),\(K = 1\),\(w_i = 1\) | | 3 | \(N \le 1000\),\(M \le 5000\),\(K \le 10\),\(w_i = 1\) | | 4 | \(N \le 10000\),\(M \le 50000\),\(K \le 10\),\(w_i = 1\) | | 5 | \(N \le 100000\),\(M \le 200000\),\(K \le 10\),\(w_i = 1\) | | 6 | \(N \le 100000\),\(M \le 200000\),\(K \le 10\),\(w_i \le 3\) | | 7 | \(N \le 100000\),\(K \le 10\),\(w_i \le 100\),保证地图为一棵树 | | 8 | \(N \le 100000\),\(M \le 200000\),\(K \le 16\),\(w_i = 1\) | | 9 | \(N \le 100000\),\(M \le 200000\),\(K \le 16\),\(w_i \le 100\) | | 10 | \(N \le 100000\),\(M \le 200000\),\(K \le 16\),\(w_i \le 100\) |

zqy2018's solution

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m, k, pos[20];
int dis[17][100005], f[17][65537];
int at[100005] = {0}, nxt[400005], w[400005], to[400005], cnt = 0;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq[17];
queue<int> q;
int logg[65537];
bool vis[65537] = {0};
inline int lowbit(int x){
    return x & (-x);
}
void init(){
    n = read(), m = read(), k = read();
    for (int i = 0; i < k; ++i)
        pos[i] = read();
    for (int i = 1; i <= m; ++i){
        int u = read(), v = read(), ww = read();
        to[++cnt] = v, nxt[cnt] = at[u], w[cnt] = ww, at[u] = cnt;
        to[++cnt] = u, nxt[cnt] = at[v], w[cnt] = ww, at[v] = cnt;
    }
    memset(f, 0x3f, sizeof(f));
    memset(dis, 0x02, sizeof(dis));
    for (int i = 0; i < k; ++i)
        logg[1 << i] = i;
}
void dij(int st, int id){
    int *d = dis[id];
    d[st] = 0;
    pq[id].push(make_pair(0, st));
    for (int i = 1; i <= n; ++i){
        while (!pq[id].empty()){
            if (pq[id].top().first > d[pq[id].top().second])
                pq[id].pop();
            else break;
        }
        int minp = pq[id].top().second, dd = d[minp];
        pq[id].pop();
        for (int j = at[minp]; j; j = nxt[j]){
            if (d[to[j]] > dd + w[j])
                d[to[j]] = dd + w[j], pq[id].push(make_pair(d[to[j]], to[j]));
        } 
    }
}
void solve(){
    for (int i = 0; i < k; ++i)
        dij(pos[i], i);
    dij(1, k);
    if (k == 0) {
        int ans = dis[0][n];
        printf("%d\n", (ans == 0x02020202 ? -1: ans));
        return ;
    }
    for (int i = 0; i < k; ++i)
        f[i][(1 << i)] = dis[k][pos[i]], q.push(1 << i);
    while (!q.empty()){
        int h = q.front();
        q.pop();
        for (int i = 0; i < k; ++i){
            int j = (1 << i);
            if (j & h) continue;
            int tmp = h, lbt;
            while (tmp > 0){
                lbt = lowbit(tmp);
                f[i][h | j] = min(f[i][h | j], f[logg[lbt]][h] + dis[logg[lbt]][pos[i]]);
                tmp -= lbt;
            }
            if (!vis[h | j])
                vis[h | j] = true, q.push(h | j);
        }
    }
    int ans = 0x02020202;
    for (int i = 0; i < k; ++i)
        ans = min(ans, dis[i][n] + f[i][(1 << k) - 1]);
    printf("%d\n", (ans == 0x02020202 ? -1: ans));
}
int main(){
    init();
    solve();
    return 0;
}