이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// ~Be name khoda~ //
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define cl clear
#define endll '\n'
const int maxn = 1e6 + 10;
const int maxn5 = 2e3 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 2e18;
ll h1[maxn5], h2[maxn5];
pair <ll, ll> dis[maxn5][2][maxn5];
int root[maxn5][2][maxn5];
int pa[maxn5];
set <pair<ll, pair<int, int>>> av;
vector <pair<int, int>> adj[maxn5];
int a[maxn5], b[maxn5];
ll c[maxn5];
int x[maxn];
pair <ll, ll> done[maxn];
int mxx[maxn];
int n;
inline void dij(int e, bool ty){
for(int i = 0; i < n; i++){
h1[i] = h2[i] = inf;
}
memset(pa, -1, sizeof pa);
int uu = a[e], vu = b[e];
if(ty){
uu = b[e];
vu = a[e];
}
bool ch = false;
h1[vu] = 0;
pa[vu] = e;
av.clear();
for(int i = 0; i < n; i++){
av.insert({h1[i], {i, 0}});
av.insert({h2[i], {i, 1}});
}
while(!av.empty()){
int v = av.begin() -> se.fi, ty = av.begin() -> se.se;
av.erase(av.begin());
if(ch){
cout << v << ' ' << ty << ' ' << h1[v] << ' ' << h2[v] << ' ' << pa[v] << '\n';
}
if(ty == 0){
if(h1[v] >= inf)
continue;
for(auto p : adj[v]) if(p.se != pa[v] && (v != uu || p.fi != vu)){
int u = p.fi;
ll val = h1[v] + c[p.se];
if(val <= h1[u]){
av.erase({h1[u], {u, 0}});
av.erase({h2[u], {u, 1}});
h2[u] = h1[u];
h1[u] = val;
pa[u] = p.se;
av.insert({h1[u], {u, 0}});
av.insert({h2[u], {u, 1}});
}
else if(val < h2[u]){
av.erase({h2[u], {u, 1}});
h2[u] = val;
av.insert({h2[u], {u, 1}});
}
}
}
else{
if(h2[v] >= inf)
continue;
int i = pa[v];
int u = a[i] == v ? b[i] : a[i];
if(v != uu || u != vu){
ll val = h2[v] + c[i];
if(val <= h1[u]){
av.erase({h1[u], {u, 0}});
av.erase({h2[u], {u, 1}});
h2[u] = h1[u];
h1[u] = val;
pa[u] = i;
av.insert({h1[u], {u, 0}});
av.insert({h2[u], {u, 1}});
}
else if(val < h2[u]){
av.erase({h2[u], {u, 1}});
h2[u] = val;
av.insert({h2[u], {u, 1}});
}
}
}
}
for(int i = 0; i < n; i++){
dis[e][ty][i] = {h1[i], h2[i]};
root[e][ty][i] = pa[i];
}
}
inline bool get_ty(int e, int u, int v){
return a[e] == v;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int m, t, l; cin >> n >> m >> t >> l;
for(int i = 0; i < m; i++){
cin >> a[i] >> b[i] >> c[i];
a[i]--; b[i]--;
adj[a[i]].pb({b[i], i});
adj[b[i]].pb({a[i], i});
}
for(int i = 0; i < m; i++){
dij(i, 0);
dij(i, 1);
}
for(int i = 0; i < l; i++){
cin >> x[i];
x[i]--;
}
int a, b; cin >> a >> b;
a--; b--;
x[a] = b;
/*
for(int i = 0; i < m; i++) for(int j = 0; j < n; j++){
cout << ::a[i] << ' ' << ::b[i] << " * " << j << ' ' << dis[i][0][j].fi << ' ' << dis[i][0][j].se << endl;
cout << dis[i][1][j].fi << ' ' << dis[i][1][j].se << ' ' << root[i][1][j] << endl;
}
//*/
for(int i = 0; i < l; i++){
if(i == 0){
done[0] = {0, 0};
mxx[0] = adj[x[0]][0].se;
}
else{
int u = x[i - 1], v = x[i];
done[i].fi = inf;
int opt = mxx[i - 1];
for(auto p : adj[u]){
int z = p.fi, id = p.se;
ll val, val2;
if(id != mxx[i - 1]){
val = done[i - 1].fi + dis[id][get_ty(id, u, z)][v].fi + c[id];
val2 = done[i - 1].fi + dis[id][get_ty(id, u, z)][v].se + c[id];
}
else{
val = done[i - 1].se + dis[id][get_ty(id, u, z)][v].fi + c[id];
val2 = done[i - 1].se + dis[id][get_ty(id, u, z)][v].se + c[id];
}
if(val <= done[i].fi){
opt = id;
done[i].fi = val;
done[i].se = val2;
mxx[i] = root[id][get_ty(id, u, z)][v];
}
}
for(auto p : adj[u]){
int z = p.fi, id = p.se;
ll val = (root[id][get_ty(id, u, z)][v] == mxx[i] ? dis[id][get_ty(id, u, z)][v].se : dis[id][get_ty(id, u, z)][v].fi) + c[id];
//cout << "alright " << z << ' ' << id << ' ' << val << ' ' << done[i].se << endl;
if(id != mxx[i - 1]){
val += done[i - 1].fi;
}
else{
val += done[i - 1].se;
}
if(val <= done[i].se){
done[i].se = val;
}
}
}
//cout << i << ' ' << x[i] << ' ' << done[i].fi << ' ' << done[i].se << ' ' << mxx[i] << endl;
}
cout << (done[l - 1].fi == inf ? -1 : done[l - 1].fi) << endl;
}
/*
4 4 4 3
1 2 1
2 3 1
1 3 1
1 4 1
2
1
2
2 4
*/
컴파일 시 표준 에러 (stderr) 메시지
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:167:8: warning: variable 'opt' set but not used [-Wunused-but-set-variable]
167 | int opt = mxx[i - 1];
| ^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |