#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;
const LL llinf=2e18;
int n, m, q, len;
int num[2010][2010], re;
vector<pii> link[2010];
LL dist[4010][4010];
bool ch[4010];
priority_queue<pair<LL, pii>, vector<pair<LL, pii> >, greater<pair<LL, pii> > > pq;
void do_dijk(int s, int e){
memset(ch, 0, sizeof ch);
pq.push(mp(0ll, mp(s, e)));
dist[num[s][e]][num[s][e]]=0;
while(!pq.empty()){
LL d=pq.top().F;
int fr=pq.top().S.F, nw=pq.top().S.S;
pq.pop();
if(ch[num[fr][nw]])continue;
ch[num[fr][nw]]=true;
for(auto j:link[nw]){
if(j.F!=fr&&dist[num[s][e]][num[fr][nw]]>d+j.S){
dist[num[s][e]][num[fr][nw]]=d+j.S;
pq.push(mp(d+j.S, mp(nw, j.F)));
}
}
}
}
int arr[100010];
struct NODE{
pair<LL, pii> p[4];
NODE(){for(int i=0; i<4; i++)p[i]=mp(llinf, mp(1, 1));}
}proc[2010][2010], tree[400010];
NODE f(NODE a, NODE b){
NODE ret;
vector<pair<LL, pii> > vc;
for(int i=0; i<4; i++){
for(int j=0; j<4; j++){
if(a.p[i].S.S==b.p[j].S.F)vc.eb(mp(llinf, mp(1, 1)));
else vc.eb(mp(a.p[i].F+b.p[j].F, mp(a.p[i].S.F, b.p[j].S.S)));
}
}
for(auto k:vc)ret.p[0]=min(ret.p[0], k);
for(auto k:vc){
if(k.S.F!=ret.p[0].S.F&&k.S.S!=ret.p[0].S.S)
ret.p[1]=min(ret.p[1], k);
}
for(auto k:vc){
if(k.S.F!=ret.p[1].S.F&&k.S.S!=ret.p[0].S.S)
ret.p[2]=min(ret.p[2], k);
}
for(auto k:vc){
if(k.S.F!=ret.p[0].S.F&&k.S.S!=ret.p[1].S.S)
ret.p[3]=min(ret.p[3], k);
}
return ret;
}
void init(int point, int s, int e){
if(s==e){
tree[point]=proc[arr[s]][arr[s+1]];
return;
}
init(point*2, s, (s+e)/2);
init(point*2+1, (s+e)/2+1, e);
tree[point]=f(tree[point*2], tree[point*2+1]);
}
void update(int point, int s, int e, int num){
if(s==e){
tree[point]=proc[arr[s]][arr[s+1]];
return;
}
if(num<=(s+e)/2)update(point*2, s, (s+e)/2, num);
else update(point*2+1, (s+e)/2+1, e, num);
tree[point]=f(tree[point*2], tree[point*2+1]);
}
int main(){
scanf("%d %d %d %d", &n, &m, &q, &len);
for(int i=1; i<=m; i++){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
link[a].eb(b, c);
num[a][b]=++re;
link[b].eb(a, c);
num[b][a]=++re;
}
for(int i=1; i<=re; i++){
for(int j=1; j<=re; j++)dist[i][j]=llinf;
}
for(int i=1; i<=n; i++){
for(auto j:link[i])do_dijk(i, j.F);
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(i==j)continue;
vector<pair<LL, pii> > vc;
for(auto k1:link[i]){
for(auto k2:link[j]){
vc.eb(dist[num[i][k1.F]][num[k2.F][j]]+k1.S, mp(k1.F, k2.F));
}
}
for(auto k:vc)proc[i][j].p[0]=min(proc[i][j].p[0], k);
for(auto k:vc){
if(k.S.F!=proc[i][j].p[0].S.F&&k.S.S!=proc[i][j].p[0].S.S)
proc[i][j].p[1]=min(proc[i][j].p[1], k);
}
for(auto k:vc){
if(k.S.F!=proc[i][j].p[1].S.F&&k.S.S!=proc[i][j].p[0].S.S)
proc[i][j].p[2]=min(proc[i][j].p[2], k);
}
for(auto k:vc){
if(k.S.F!=proc[i][j].p[0].S.F&&k.S.S!=proc[i][j].p[1].S.S)
proc[i][j].p[3]=min(proc[i][j].p[3], k);
}
}
}
for(int i=1; i<=len; i++)scanf("%d", &arr[i]);
init(1, 1, len-1);
while(q--){
int a, b;
scanf("%d %d", &a, &b);
arr[a]=b;
if(a<len)update(1, 1, len-1, a);
if(a>1)update(1, 1, len-1, a-1);
printf("%lld\n", tree[1].p[0].F>=llinf?-1:tree[1].p[0].F);
}
}
Compilation message
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:88:10: 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, &len);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &a, &b, &c);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:127:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1; i<=len; i++)scanf("%d", &arr[i]);
~~~~~^~~~~~~~~~~~~~~
wild_boar.cpp:131:14: 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 |
164 ms |
278520 KB |
Output is correct |
| 2 |
Incorrect |
153 ms |
278520 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
164 ms |
278520 KB |
Output is correct |
| 2 |
Incorrect |
153 ms |
278520 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
164 ms |
278520 KB |
Output is correct |
| 2 |
Incorrect |
153 ms |
278520 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
164 ms |
278520 KB |
Output is correct |
| 2 |
Incorrect |
153 ms |
278520 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
