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;
}