/*
Always took the second best answer.
Let's call g2(A) is the second smallest number of an arbitrary set A.
Subtask 1:
f[node] = g2(f[c_i] + len(node, c_i))
Subtask 2:
Make a new data structure that support:
- Storing the two smallest number of the set
- Allowing update: add one new number to the set.
(don't need to store the whole set, just need the two smallest number)
f[exit node] = {0, 0}. f[others] = {oo, oo}
when poppin a node from pq:
- when processing a child C:
val = f[child]
val.add(f[node].p2 + len(node, child))
if better:
assign
if there are at least two choices in the set:
push to pq.
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 1000001
#define fi first
#define se second
#define FOR(type, i, a, b) for(type i = (a); i <= (b); i++)
#define FORD(type, i, b, a) for(type i = (b); i >= (a); i--)
//================================================================
const ll oo = 1e18;
struct Node
{
int node, len;
Node() {node = len = 0;}
Node(int node, int len) {this -> node = node, this -> len = len;}
};
typedef vector<Node> vg;
int n, m, k;
vector<Node> graph[MAX];
int exits[MAX];
bool isExit[MAX];
int checkSubtask(){
if (m == n - 1) return 1;
if (m <= 100000) return 2;
return 3;
}
//===========================================================
ll f1[MAX];
ll dfs1(int node, int parent){
ll &ans = f1[node];
if (isExit[node]) return ans = 0;
vector<ll> save;
for (Node ch: graph[node]){
int child = ch.node;
if (child == parent) continue;
ll tmp = dfs1(child, node);
if (tmp < oo)
save.push_back(tmp + ch.len);
}
if (save.size() < 2) return false;
sort(save.begin(), save.end());
return save[1];
}
void sub1(){
memset(f1, 0x3f, sizeof(f1));
cout << dfs1(0, 0);
}
//===========================================================
struct Best{
ll p1 = oo, p2 = oo;
Best(){
p1 = p2 = oo;
}
Best(int p1, int p2): p1(p1), p2(p2){}
bool ok(){
return p1 != oo and p2 != oo;
}
void add(int num){
if (num <= p1)
p2 = p1, p1 = num;
else if (num <= p2)
p2 = num;
}
};
bool operator < (Best a, Best b){
return (a.p2 != b.p2) ? (a.p2 < b.p2) : (a.p1 < b.p1);
}
bool operator > (Best a, Best b){
return (a.p2 != b.p2) ? (a.p2 > b.p2) : (a.p1 > b.p1);
}
bool operator == (Best a, Best b){
return a.p1 == b.p1 and a.p2 == b.p2;
}
bool operator != (Best a, Best b){
return not (a == b);
}
Best f[MAX];
typedef pair<Best, int> Data;
priority_queue<Data, vector<Data>, greater<Data>> pq;
void init(){
FOR(int, i, 0, n - 1)
if (isExit[i])
f[i] = {0, 0},
pq.push({f[i], i});
else
f[i] = Best();
}
void sub23(){
init();
while (!pq.empty()){
pair<Best, int> cur = pq.top(); pq.pop();
int node = cur.se; Best val = cur.fi;
if (val != f[node]) continue;
for (Node ch: graph[node]){
int child = ch.node;
int edgeVal = val.p2 + ch.len;
Best childVal = f[child]; childVal.add(edgeVal);
if (childVal < f[child]){
f[child] = childVal;
if (f[child].ok())
pq.push({f[child], child});
}
}
}
cout << f[0].p2;
}
//===========================================================
void input();
main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
input();
int subtask = checkSubtask();
if (subtask == 1)
sub1();
else
sub23();
}
void input(){
cin >> n >> m >> k;
FOR(int, i, 1, m){
int u, v, l; cin >> u >> v >> l;
graph[u].push_back({v, l});
graph[v].push_back({u, l});
}
FOR(int, i, 0, k - 1){
int u; cin >> u;
exits[i] = u;
isExit[u] = true;
}
}
Compilation message
crocodile.cpp:142:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
142 | main()
| ^~~~
/usr/bin/ld: /tmp/cc5D8rGC.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccmyBmPD.o:crocodile.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc5D8rGC.o: in function `main':
grader.cpp:(.text.startup+0x36): undefined reference to `travel_plan(int, int, int (*) [2], int*, int, int*)'
collect2: error: ld returned 1 exit status
