#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];
vector<int> S[100100], E[100100], in[2020], out[2020];
vector<ll> W[100100];
int X[100100];
ll dp[100100][4];
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;
res[s] = F[abs(s)];
pq.push({F[abs(s)], s, 0});
// printf("dijkstra from %d:\n", s);
while(!pq.empty()){
auto [dist, cur, p] = pq.top(); pq.pop();
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){
pq.push({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;
}
}
}
void initW(int p, ll (*dist)[4040]){
W[p].push_back(INF);
S[p].push_back(-1);
E[p].push_back(-1);
for (auto &s1:out[X[p]]){
for (auto &e1:in[X[p+1]]){
if (W[p].back() > dist[s1][e1]){
W[p].back() = dist[s1][e1];
S[p].back() = s1;
E[p].back() = e1;
}
}
}
W[p].push_back(INF);
S[p].push_back(-1);
E[p].push_back(-1);
for (auto &s2:out[X[p]]) if (s2!=S[p][0]){
for (auto &e2:in[X[p+1]]) if (e2!=E[p][0]){
if (W[p].back() > dist[s2][e2]){
W[p].back() = dist[s2][e2];
S[p].back() = s2;
E[p].back() = e2;
}
}
}
W[p].push_back(INF);
S[p].push_back(-1);
E[p].push_back(-1);
for (auto &s3:out[X[p]]) if (s3!=S[p][0]){
for (auto &e3:in[X[p+1]]) if (e3!=E[p][1]){
if (W[p].back() > dist[s3][e3]){
W[p].back() = dist[s3][e3];
S[p].back() = s3;
E[p].back() = e3;
}
}
}
W[p].push_back(INF);
S[p].push_back(-1);
E[p].push_back(-1);
for (auto &s4:out[X[p]]) if (s4!=S[p][1]){
for (auto &e4:in[X[p+1]]) if (e4!=E[p][0]){
if (W[p].back() > dist[s4][e4]){
W[p].back() = dist[s4][e4];
S[p].back() = s4;
E[p].back() = e4;
}
}
}
// printf("init %d to %d -> ", X[p], X[p+1]);
// for (int i=0;i<4;i++){
// printf("(%lld / %d, %d) ", W[p][i], S[p][i], E[p][i]);
// }
// printf("\n");
}
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);
}
ll (*dist)[4040] = (ll (*)[4040])(&(dist0[2020][2020]));
ll *res = res0 + 2020;
// printf(" What %d %d\n", &(dist[1][-1]), &(dist0[2021][2019]));
for (int i=1;i<=m;i++){
dijkstra(m, i, dist, res, adj);
// if (i==1) printf(" WTF %lld\n", res[-2]);
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];
}
// printf("WTFF %lld (%d / %d)\n", dist[1][-2], &(dist[1][-2]), &(dist0[2021][2018]));
for (int i=1;i<=l;i++) scanf("%d", X+i);
int pp, qq;
scanf("%d %d", &pp, &qq);
X[pp] = qq;
for (int i=1;i<l;i++){
initW(i, dist);
for (int j=0;j<4;j++){
dp[i+1][j] = INF;
if (i==1) {dp[i+1][j] = W[1][j]; continue;}
if (W[i][j]==INF) continue;
for (int k=0;k<4;k++) if (abs(E[i-1][k])!=abs(S[i][j])){
dp[i+1][j] = min(dp[i+1][j], dp[i][k] + W[i][j]);
}
}
}
printf("%lld\n", *min_element(dp[l], dp[l]+4));
}
Compilation message
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:128:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
128 | scanf("%d %d %d %d", &n, &m, &q, &l);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:133:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
133 | scanf("%d %d %d", &x, &y, &z);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:164:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
164 | for (int i=1;i<=l;i++) scanf("%d", X+i);
| ~~~~~^~~~~~~~~~~
wild_boar.cpp:166:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
166 | scanf("%d %d", &pp, &qq);
| ~~~~~^~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
7636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
