#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;
vector<pair<int, int>> adj0[6060];
pair<int, int> Edge[2020];
ll dist0[4040][4040], res0[4040];
int visited0[6060], F[2020];
ll (*dist)[4040];
vector<int> in[2020], out[2020];
int X[100100];
ll dp[100100][4];
struct Node{
ll W[4][4];
int S[4], E[4];
Node(){}
ll ans(){
ll ret = INF;
for (int i=0;i<4;i++){
for (int j=0;j<4;j++){
ret = min(ret, W[i][j]);
}
}
return ret==INF?-1:ret;
}
Node operator + (const Node &N) const{
Node ret;
memset(ret.W[0], 0x3f, sizeof(ll) * 16);
for (int k2=0;k2<4;k2++){
for (int i=0;i<4;i++){
ll mn = INF;
for (int k1=0;k1<4;k1++) if (abs(E[k1])!=abs(N.S[k2])) mn = min(mn, W[i][k1]);
for (int j=0;j<4;i++) ret.W[i][j] = min(ret.W[i][j], mn + N.W[k2][j]);
}
ret.S[k2] = S[k2];
ret.E[k2] = N.E[k2];
}
return ret;
}
};
Node initW(int p);
struct Seg{
Node tree[400400];
void init(int i, int l, int r){
if (l==r){
tree[i] = initW(l);
return;
}
int m = (l+r)>>1;
init(i<<1, l, m); init(i<<1|1, m+1, r);
tree[i] = tree[i<<1] + tree[i<<1|1];
}
void update(int i, int l, int r, int p){
if (r<p || p<l) return;
if (l==r){
tree[i] = initW(l);
return;
}
int m = (l+r)>>1;
update(i<<1, l, m, p); update(i<<1|1, m+1, r, p);
tree[i] = tree[i<<1] + tree[i<<1|1];
}
}tree;
void dijkstra(int m, int s, ll (*dist)[4040], ll *res, vector<pair<int, int>> *adj){
int *visited = visited0 + 2020;
fill(res-2020, res+2020, INF);
fill(visited-2020, visited+4040, -1);
priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
vector<array<ll, 3>> st;
res[s] = F[abs(s)];
pq.push({F[abs(s)], s, 0});
while(!pq.empty() || !st.empty()){
array<ll, 3> tmp;
if (!st.empty()) {tmp = st.back(); st.pop_back();}
else {tmp = pq.top(); pq.pop();}
auto [dist, cur, p] = tmp;
if (visited[cur]==-2) continue;
if (visited[cur]==-1){
if (cur <= m){
// printf(" dist[%lld] = %lld\n", cur, res[cur]);
visited[cur] = -2;
for (auto &[v, w]:adj[cur]) if (visited[v]!=-2){
st.push_back({dist, v, cur});
}
}
else{
visited[cur] = abs(p);
for (auto &[v, w]:adj[cur]) if (visited[v]!=-2 && abs(v)!=abs(p)){
res[v] = dist + w;
pq.push({res[v], v, cur});
}
}
}
else{
for (auto &[v, w]:adj[cur]) if (abs(v)==visited[cur] && visited[v]!=-2){
res[v] = dist + w;
pq.push({res[v], v, cur});
}
visited[cur] = -2;
}
}
}
map<int, Node> mp[2020];
Node initW(int p){
vector<ll> W;
vector<int> S, E;
if (mp[X[p]].find(X[p+1])!=mp[X[p]].end()){
return mp[X[p]][X[p+1]];
}
W.push_back(INF);
S.push_back(-1);
E.push_back(-1);
for (auto &s1:out[X[p]]){
for (auto &e1:in[X[p+1]]){
if (W.back() > dist[s1][e1]){
W.back() = dist[s1][e1];
S.back() = s1;
E.back() = e1;
}
}
}
W.push_back(INF);
S.push_back(-1);
E.push_back(-1);
for (auto &s2:out[X[p]]) if (s2!=S[0]){
for (auto &e2:in[X[p+1]]) if (e2!=E[0]){
if (W.back() > dist[s2][e2]){
W.back() = dist[s2][e2];
S.back() = s2;
E.back() = e2;
}
}
}
W.push_back(INF);
S.push_back(-1);
E.push_back(-1);
for (auto &s3:out[X[p]]) if (s3!=S[0]){
for (auto &e3:in[X[p+1]]) if (e3!=E[1]){
if (W.back() > dist[s3][e3]){
W.back() = dist[s3][e3];
S.back() = s3;
E.back() = e3;
}
}
}
W.push_back(INF);
S.push_back(-1);
E.push_back(-1);
for (auto &s4:out[X[p]]) if (s4!=S[1]){
for (auto &e4:in[X[p+1]]) if (e4!=E[0]){
if (W.back() > dist[s4][e4]){
W.back() = dist[s4][e4];
S.back() = s4;
E.back() = e4;
}
}
}
Node ret;
for (int i=0;i<4;i++){
for (int j=0;j<4;j++){
if (i!=j) ret.W[i][j] = INF;
else ret.W[i][j] = W[i];
}
ret.S[i] = S[i];
ret.E[i] = E[i];
}
mp[X[p]][X[p+1]] = ret;
return ret;
}
int main(){
int n, m, q, l;
scanf("%d %d %d %d", &n, &m, &q, &l);
vector<pair<int, int>> *adj = adj0 + m;
for (int i=1;i<=m;i++){
int x, y, z;
scanf("%d %d %d", &x, &y, &z);
Edge[i] = {x, y}; F[i] = z;
adj[i].emplace_back(y+m, 0);
adj[-i].emplace_back(x+m, 0);
adj[x+m].emplace_back(i, z);
adj[y+m].emplace_back(-i, z);
out[x].push_back(i);
out[y].push_back(-i);
in[x].push_back(-i);
in[y].push_back(i);
}
dist = (ll (*)[4040])(&(dist0[2020][2020]));
ll *res = res0 + 2020;
for (int i=1;i<=m;i++){
dijkstra(m, i, dist, res, adj);
for (int j=-m;j<=m;j++) dist[i][j] = res[j];
dijkstra(m, -i, dist, res, adj);
for (int j=-m;j<=m;j++) dist[-i][j] = res[j];
}
for (int i=1;i<=l;i++) scanf("%d", X+i);
tree.init(1, 1, l-1);
while(q--){
int pp, qq;
scanf("%d %d", &pp, &qq);
X[pp] = qq;
if (pp > 1) tree.update(1, 1, l-1, pp-1);
if (pp < l) tree.update(1, 1, l-1, pp);
printf("%lld\n", tree.tree[1].ans());
}
}
Compilation message
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:211:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
211 | scanf("%d %d %d %d", &n, &m, &q, &l);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:216:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
216 | scanf("%d %d %d", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:243:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
243 | for (int i=1;i<=l;i++) scanf("%d", X+i);
| ~~~~~^~~~~~~~~~~
wild_boar.cpp:248:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
248 | scanf("%d %d", &pp, &qq);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18031 ms |
724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18031 ms |
724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18031 ms |
724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
18031 ms |
724 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
