#include "crocodile.h"
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "crocodile"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 3e5 + 9;
int n, m, k;
vector<int> g[MAXN], exitVertice;
iii edge[MAXN];
int deg[MAXN], isExit[MAXN], special[MAXN], bad[MAXN];
int NumNode, NumEdge, NumCmp = 0;
set<ii> optimal[MAXN];
namespace subtask2{
bool checkSubtask2(){
return n <= 1000 and m <= 100000;
}
int dist[1003][1003];
void dijkstra(int s){
memset(dist[s], 0x3f, sizeof(dist[s]));
priority_queue<ii, vector<ii>, greater<ii>> pq;
pq.push({0, s});
dist[s][s] = 0;
while(!pq.empty()){
int du = pq.top().fi;
int u = pq.top().se;
// cout << u << ' ' << du << endl;
pq.pop();
for(auto id: g[u]){
int v = edge[id].se.fi + edge[id].se.se - u;
if (minimize(dist[s][v], dist[s][u] + edge[id].fi)){
pq.push({dist[s][v], v});
}
}
}
}
int go(){
int cur = 0, prvEdge = -1, ans = 0;
while(isExit[cur] == 0){
int tryed = 0;
// cerr << cur << ' ';
while(!optimal[cur].empty()){
int id = (*optimal[cur].begin()).se;
tryed++;
// cout << (*optimal[cur].begin()).fi << ' ' << cur << ' ' << id << endl;
optimal[cur].erase(optimal[cur].begin());
if ((id != prvEdge and tryed == 1) or id == prvEdge) continue;
cur = edge[id].se.fi + edge[id].se.se - cur;
prvEdge = id;
ans += edge[id].fi;
// cout << "?" << id << ' ' << edge[id].fi << endl;
break;
}
}
return ans;
}
int solveSubtask2(){
for(int i = 1; i < n; i++){
if (deg[i] == 2 and isExit[i] == 0) bad[i] = true;
}
// for(int i = 0; i < n; i++){
// cout << bad[i] << ' ';
// }
// cout << endl;
for(int i = 1; i <= m; i++){
int u = edge[i].se.fi;
int v = edge[i].se.se;
if (bad[u] or bad[v]) continue;
g[u].pb(i);
g[v].pb(i);
}
for(int i = 0; i < n; i++){
dijkstra(i);
}
// for(int i = 0; i < n; i++){
// for(int j = 0; j < n; j++){
// cout << dist[i][j] << ' ';
// }
// cout << endl;
// }
// cout << endl;
for(int i = 1; i <= m; i++){
int u = edge[i].se.fi;
int v = edge[i].se.se;
int w = edge[i].fi;
if (bad[u] or bad[v]) continue;
// cout << u << ' ' << v << ' ' << isExit[u] << ' ' <<isExit[v] << endl;
if (isExit[v]) {
// cout << w << ' ' << u << ' ' << v << ' ' << i << endl;
optimal[u].insert({w, i});
}
if (isExit[u]) optimal[v].insert({w, i});
for(int j = 1; j <= k; j++){
int x = exitVertice[j - 1];
if (x != v) optimal[u].insert({dist[v][x] + w, i});
if (x != u) optimal[v].insert({dist[u][x] + w, i});
while(optimal[u].size() > 3) optimal[u].erase(--optimal[u].end());
while(optimal[v].size() > 3) optimal[v].erase(--optimal[v].end());
}
}
return go();
// return 0;
}
}
int travel_plan(int N, int M, int R[][2], int W[], int K, int E[]){
n = N, m = M;
for(int i = 0; i < m; i++){
edge[i + 1].fi = W[i];
deg[R[i][0]]++;
deg[R[i][1]]++;
edge[i + 1].se = {R[i][0], R[i][1]};
}
k = K;
for(int i = 1; i <= k; i++){
exitVertice.pb(E[i - 1]);
isExit[E[i - 1]] = true;
}
if (subtask2::checkSubtask2()) return subtask2::solveSubtask2();
}
/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
- Nho sinh test de tranh RTE / TLE
--> Coi lai truoc khi nop
**/
Compilation message
crocodile.cpp: In function 'void subtask2::dijkstra(long long int)':
crocodile.cpp:44:20: warning: unused variable 'du' [-Wunused-variable]
44 | int du = pq.top().fi;
| ^~
crocodile.cpp: In function 'long long int travel_plan(long long int, long long int, long long int (*)[2], long long int*, long long int, long long int*)':
crocodile.cpp:156:1: warning: control reaches end of non-void function [-Wreturn-type]
156 | }
| ^
/usr/bin/ld: /tmp/ccfvBAhH.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
