#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>
using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<ll, int> pli;
int N, M, T, L;
t3 edgen[4040];
int edgec[2020][2020];
vector <pii> IE[2020];
vector <int> nume[2020];
vector <int> numl[2020], numr[2020];
vector <pii> E[20020];
int cs;
void addedge(int x, int y, int c) {
E[x].pb(pii(c, y));
}
ll dis[4040][4040], dtemp[12020];
int X[100010];
pii query[100010];
pll tmn[4040][2020][2];
int main() {
memset(edgec, -1, sizeof edgec);
scanf("%d%d%d%d", &N, &M, &T, &L);
rep(i, M) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
edgen[i<<1] = t3(x, y, z);
edgec[x][y] = i<<1;
edgen[i<<1|1] = t3(y, x, z);
edgec[y][x] = i<<1|1;
nume[x].pb(cs++);
nume[y].pb(cs++);
IE[x].pb(pii(z, y));
IE[y].pb(pii(z, x));
}
cs = 2 * M;
for(int i=1;i<=N;i++) {
int l = szz(IE[i]);
numl[i].resize(l);
numr[i].resize(l);
rep(j, l) numl[i][j] = cs++;
rep(j, l) numr[i][j] = cs++;
for(int j=1;j<l;j++) {
int x = numl[i][j-1], y = numl[i][j];
addedge(y, x, 0);
x = numr[i][j-1], y = numr[i][j];
addedge(x, y, 0);
}
rep(j, l) {
addedge(numl[i][j], nume[i][j], 0);
addedge(numr[i][j], nume[i][j], 0);
}
rep(j, l) {
int x = nume[i][j] ^ 1, len = get<2>(edgen[x]);
if(j) addedge(x, numl[i][j-1], len);
if(j < l-1) addedge(x, numr[i][j+1], len);
}
}
rep(st, 2*M) {
rep(i, cs) dtemp[i] = 1e18;
dtemp[st] = 0;
priority_queue <pli, vector<pli>, greater<pli> > pq;
pq.push(pli(0, st));
while(!pq.empty()) {
pli t = pq.top(); pq.pop();
if(dtemp[t.Se] != t.Fi) continue;
for(pii e : E[t.Se]) {
if(t.Fi + e.Fi < dtemp[e.Se]) {
dtemp[e.Se] = t.Fi + e.Fi;
pq.push(pli(dtemp[e.Se], e.Se));
}
}
}
rep(i, 2*M) dis[st][i] = dtemp[i];
}
rep(i, 4040) rep(j, 2020) rep(k, 2) tmn[i][j][k] = pll(1e18, -1);
for(int i=1;i<=N;i++) for(int j=1;j<=N;j++) {
int si = szz(IE[i]);
int sj = szz(IE[j]);
rep(k, si) {
int eidx = nume[i][k];
rep(l, sj) {
int fidx = nume[j][l] ^ 1;
pll p = pll(dis[eidx][fidx], get<0>(edgen[fidx]));
if(tmn[eidx][j][0] > p) tmn[eidx][j][1] = tmn[eidx][j][0], tmn[eidx][j][0] = p;
else if(tmn[eidx][j][1] > p) tmn[eidx][j][1] = p;
}
}
}
for(int i=1;i<=L;i++) scanf("%d", X+i);
for(int i=1;i<=T;i++) {
int x, y; scanf("%d%d", &x, &y);
query[i] = pii(x, y);
}
if(T > 1) return 0;
X[query[1].Fi] = query[1].Se;
int ST = X[1];
ll dp[2020] = {}, tdp[2020];
for(int i=1;i<=N;i++) dp[i] = 1e18;
for(int i=1;i<=N;i++) {
if(edgec[ST][i] != -1) dp[i] = 0;
}
for(int i=2;i<=L;i++) {
int pre = X[i-1], nxt = X[i];
for(int j=1;j<=N;j++) tdp[j] = 1e18;
for(int j=1;j<=N;j++) if(dp[j] < 1e17) {
int eidx = edgec[pre][j];
rep(u, 2) if(tmn[eidx][nxt][u].Fi < 1e17) {
int fj = (int)tmn[eidx][nxt][u].Se;
tdp[fj] = min(tdp[fj], dp[j] + tmn[eidx][nxt][u].Fi);
}
}
for(int j=1;j<=N;j++) if(edgec[j][nxt] != -1) {
tdp[j] += get<2>(edgen[edgec[j][nxt]]);
}
if(i == L) break;
pll wp[2]; rep(u, 2) wp[u] = pll(1e18, -1);
for(int j=1;j<=N;j++) {
pll p = pll(tdp[j], j);
if(wp[0] > p) wp[1] = wp[0], wp[0] = p;
else if(wp[1] > p) wp[1] = p;
}
for(int j=1;j<=N;j++) if(edgec[nxt][j] != -1) {
if(wp[0].Se != j) dp[j] = wp[0].Fi;
else dp[j] = wp[1].Fi;
}
// for(int j=1;j<=N;j++) printf("%lld ", dp[j]); puts("");
}
ll ans = 1e18;
for(int i=1;i<=N;i++) ans = min(ans, tdp[i]);
if(ans > 1e17) puts("-1");
else printf("%lld\n", ans);
return 0;
}
Compilation message
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:54: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, &T, &L);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &x, &y, &z);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
wild_boar.cpp:125:29: 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", X+i);
~~~~~^~~~~~~~~~~
wild_boar.cpp:127:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int x, y; scanf("%d%d", &x, &y);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
929 ms |
544996 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
929 ms |
544996 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
929 ms |
544996 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
929 ms |
544996 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
