#include <bits/stdc++.h>
#define pb push_back
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define fi first
#define se second
#define INF (1ll<<60)
using namespace std;
typedef long long LL;
typedef pair<int,int> pii;
int N, M, Q, L;
int P[101010];
int num[2020][2020], nm;
LL D[4040][4040];
bool chk[4040];
vector<pii> adj[2020];
struct Path{
int u, v;
LL w;
bool operator<(const Path &r)const{
return w > r.w;
}
};
priority_queue<Path> PQ;
struct Node{
Path p[4];
}C[2020][2020], T[404040];
void dijk(int a, int b){
PQ.push((Path){a, b, 0});
while (!PQ.empty()){
Path T = PQ.top();
PQ.pop();
if (D[num[a][b]][num[T.u][T.v]] != INF) continue;
D[num[a][b]][num[T.u][T.v]] = T.w;
for (pii x : adj[T.u]) if (x.fi != T.v) PQ.push((Path){x.fi, T.u, T.w+x.se});
}
}
Path add(Path a, Path b){
return (Path){a.u, b.v, (a.v==b.u)?INF:min(INF,a.w+b.w)};
}
Node add(Node a, Node b){
Node ret;
for (int i=0; i<4; i++) ret.p[i].w=INF;
vector<Path> v;
for (int i=0; i<4; i++) for (int j=0; j<4; j++) v.pb(add(a.p[i], b.p[j]));
for (Path x : v) ret.p[0] = max(ret.p[0], x);
for (Path x : v) if (ret.p[0].u != x.u && ret.p[0].v != x.v) ret.p[1] = max(ret.p[1], x);
for (Path x : v) if (ret.p[1].u != x.u && ret.p[0].v != x.v) ret.p[2] = max(ret.p[2], x);
for (Path x : v) if (ret.p[0].u != x.u && ret.p[1].v != x.v) ret.p[3] = max(ret.p[3], x);
return ret;
}
void init(int id, int s, int e){
if (s+1 == e){
T[id] = C[P[s]][P[e]];
return;
}
int mid=(s+e)/2;
init(id*2, s, mid), init(id*2+1, mid, e);
T[id] = add(T[id*2], T[id*2+1]);
}
void upd(int id, int s, int e, int t){
if (e < t || t < s) return;
if (s+1 == e){
T[id] = C[P[s]][P[e]];
return;
}
int mid=(s+e)/2;
upd(id*2, s, mid, t), upd(id*2+1, mid, e, t);
T[id] = add(T[id*2], T[id*2+1]);
}
int main(){
scanf("%d %d %d %d", &N, &M, &Q, &L);
for (int i=1; i<=M; i++){
int u, v, w;
scanf("%d %d %d", &u, &v, &w);
adj[u].pb(pii(v, w)), adj[v].pb(pii(u, w));
}
for (int u=1; u<=N; u++) for (pii v : adj[u]) num[u][v.fi]=++nm;
for (int i=1; i<=nm; i++) for (int j=1; j<=nm; j++) D[i][j] = INF;
for (int u=1; u<=N; u++) for (pii v : adj[u]) dijk(u, v.fi);
for (int i=1; i<=N; i++) for (int j=1; j<=N; j++){
if (i == j) continue;
for (int k=0; k<4; k++) C[i][j].p[k].w = INF;
for (pii u : adj[i]) for (pii v : adj[j]){
C[i][j].p[0] = max(C[i][j].p[0], (Path){u.fi, v.fi, D[num[u.fi][i]][num[j][v.fi]]+u.se});
}
for (pii u : adj[i]) for (pii v : adj[j]){
if (C[i][j].p[0].u == u.fi || C[i][j].p[0].v == v.fi) continue;
C[i][j].p[1] = max(C[i][j].p[1], (Path){u.fi, v.fi, D[num[u.fi][i]][num[j][v.fi]]+u.se});
}
for (pii u : adj[i]) for (pii v : adj[j]){
if (C[i][j].p[0].u == u.fi || C[i][j].p[1].v == v.fi) continue;
C[i][j].p[2] = max(C[i][j].p[2], (Path){u.fi, v.fi, D[num[u.fi][i]][num[j][v.fi]]+u.se});
}
for (pii u : adj[i]) for (pii v : adj[j]){
if (C[i][j].p[1].u == u.fi || C[i][j].p[0].v == v.fi) continue;
C[i][j].p[3] = max(C[i][j].p[3], (Path){u.fi, v.fi, D[num[u.fi][i]][num[j][v.fi]]+u.se});
}
}
for (int i=1; i<=L; i++) scanf("%d", &P[i]);
init(1, 1, L);
while(Q--){
int a, b;
scanf("%d %d", &a, &b);
P[a]=b;
upd(1, 1, N, a);
if (T[1].p[0].w >= INF) puts("-1");
else printf("%lld\n", T[1].p[0].w);
}
return 0;
}
Compilation message
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &N, &M, &Q, &L);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:84:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &u, &v, &w);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:109:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (int i=1; i<=L; i++) scanf("%d", &P[i]);
~~~~~^~~~~~~~~~~~~
wild_boar.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &a, &b);
~~~~~^~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
504 KB |
Output is correct |
| 2 |
Incorrect |
5 ms |
504 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
