#include "crocodile.h"
#include<bits/stdc++.h>
//#define ll long long
#define ll 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(ll i=a;i<=b;i++)
#define FORD(i,a,b) for(ll i=a;i>=b;i--)
#define sz(a) ((ll)(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<ll,ll> ii;
typedef pair<ll,ii> iii;
typedef vector<ll> vi;
const ll MAXN = 3e5 + 9;
ll n, m, k;
vector<ll> g[MAXN], exitVertice;
iii edge[MAXN];
ll deg[MAXN], isExit[MAXN], special[MAXN], bad[MAXN];
ll NumNode, NumEdge, NumCmp = 0;
set<ii> optimal[MAXN];
namespace subtask2{
bool checkSubtask2(){
return n <= 1000 and m <= 100000;
}
long long dist[1003][1003];
void dijkstra(ll 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()){
ll du = pq.top().fi;
ll u = pq.top().se;
// cout << u << ' ' << du << endl;
pq.pop();
for(auto id: g[u]){
ll 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});
}
}
}
}
ll go(){
ll cur = 0, prvEdge = -1, ans = 0;
while(isExit[cur] == 0){
ll tryed = 0;
// cerr << cur << ' ';
while(!optimal[cur].empty()){
ll 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(ll i = 1; i < n; i++){
if (deg[i] == 2 and isExit[i] == 0) bad[i] = true;
}
// for(ll i = 0; i < n; i++){
// cout << bad[i] << ' ';
// }
// cout << endl;
for(ll i = 1; i <= m; i++){
ll u = edge[i].se.fi;
ll v = edge[i].se.se;
if (bad[u] or bad[v]) continue;
g[u].pb(i);
g[v].pb(i);
}
for(ll i = 0; i < n; i++){
dijkstra(i);
}
// for(ll i = 0; i < n; i++){
// for(ll j = 0; j < n; j++){
// cout << dist[i][j] << ' ';
// }
// cout << endl;
// }
// cout << endl;
for(ll i = 1; i <= m; i++){
ll u = edge[i].se.fi;
ll v = edge[i].se.se;
ll 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(ll j = 1; j <= k; j++){
ll 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(ll 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(ll i = 1; i <= k; i++){
exitVertice.pb(E[i - 1]);
isExit[E[i - 1]] = true;
}
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:45:19: warning: unused variable 'du' [-Wunused-variable]
45 | ll du = pq.top().fi;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2062 ms |
35420 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2062 ms |
35420 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2062 ms |
35420 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
