This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define int long long
#define mi(x, y) (x = min(x, y))
#define ma(x, y) (x = max(x, y))
using namespace std;
vector<vector<vector<int>>> dijkstra(int s, vector<vector<pair<int, int>>>&way){
vector<vector<vector<int>>> rv((int)way.size(), vector<vector<int>>(4, vector<int>{-1, -1, -1}));
priority_queue<vector<int>> pq;
for(auto&nxt:way[s]){
pq.push({-nxt.second, nxt.first, s, nxt.first});
}
while(!pq.empty()){
int val = -pq.top()[0], ns = pq.top()[1], ne = pq.top()[2], now = pq.top()[3];
pq.pop();
int vpos = 0;
if(rv[now][0][0] != -1){
vpos = (rv[now][0][0] != ns) * 2 + (rv[now][0][1] != ne);
}
if(rv[now][vpos][0] != -1) continue;
rv[now][vpos] = {ns, ne, val};
for(auto&nxt:way[now]){
if(nxt.first != ne){
pq.push({-(val + nxt.second), ns, now, nxt.first});
}
}
}
return rv;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m, t, l; cin >> n >> m >> t >> l;
vector<vector<pair<int, int>>> way(n);
for(int i = 0; i < m; ++i){
int x, y, z; cin >> x >> y >> z; --x, --y;
way[x].push_back({y, z});
way[y].push_back({x, z});
}
vector<vector<vector<vector<int>>>> dis(n);
for(int i = 0; i < n; ++i){
dis[i] = dijkstra(i, way);
}
vector<int> trk(l);
for(int i = 0; i < l; ++i){
cin >> trk[i]; --trk[i];
}
int x, y; cin >> x >> y; --x, --y;
trk[x] = y;
vector<vector<int>> dp(l, vector<int>(4, (int)1e18));
for(int i = 0; i < 4; ++i){
dp[1][i] = dis[trk[0]][trk[1]][i][2];
}
for(int i = 1; i + 1 < l; ++i){
for(int j = 0; j < 4; ++j){
for(int k = 0; k < 4; ++k){
if(dis[trk[i - 1]][trk[i]][j][0] != -1 && dis[trk[i]][trk[i + 1]][k][0] != -1){
if(dis[trk[i - 1]][trk[i]][j][1] != dis[trk[i]][trk[i + 1]][k][0]){
mi(dp[i + 1][k], dp[i][j] + dis[trk[i]][trk[i + 1]][k][2]);
}
}
}
}
}
int ans = (int)1e18;
for(int i = 0; i < 4; ++i){
mi(ans, dp[l - 1][i]);
}
if(ans == (int)1e18) ans = -1;
cout << ans << '\n';
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |