# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1130436 | enzy | Commuter Pass (JOI18_commuter_pass) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+10;
const int inf=1e18+10;
vector<pair<int,int>>adj[maxn];
int dist[maxn][4], n, marc[maxn], best;
void dijkstra(int x, int t,int dir){
for(int i=1;i<=n;i++) dist[i][t]=inf;
dist[x][t]=0;
set<pair<int,int>>s;
for(int i=1;i<=n;i++) s.insert({dist[i][t],i});
while(!s.empty()){
auto f=s.begin();
int u=f->second;
s.erase(f);
for(auto p : adj[u]){
int viz=p.first, w=p.second;
bool flag=false;
if(dist[u][2]+w+dist[viz][3]==best||dist[u][3]+w+dist[viz][2]==best) flag=true;
if(flag&&dist[u][dir]+w==dist[viz][dir]&&dist[u][t]<dist[viz][t]){
// estou usando uma aresta já DIRECIONADA do commuter pass, então passo de graça
s.erase({dist[viz][t],viz});
dist[viz][t]=dist[u][t];
s.insert({dist[viz][t],viz});
}
if(dist[u][t]+w<dist[viz][t]){
// estou utilizando uma aresta normalmente, então tenho que pagar
s.erase({dist[viz][t],viz});
dist[viz][t]=dist[u][t]+w;
s.insert({dist[viz][t],viz});
}
}
}
}
signed main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL);
int m, s, t, u, v; cin >> n >> m >> s >> t >> u >> v;
for(int i=1;i<=m;i++){
int a, b, c; cin >> a >> b >> c;
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
int ans=dp[u][v];
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(dp[s][i]+dp[i][j]+dp[j][t]==dp[s][t]) ans=min({ans,dp[u][i]+dp[j][v],dp[v][i]+dp[j][u]});
}
dijkstra(s,2,0);
dijkstra(t,3,0);
best=dist[t][2];
for(int i=1;i<=n;i++) if(dist[i][2]+dist[i][3]==best) marc[i]++;
dijkstra(u,0,2); // direcionando todas as arestas do commuter pass de S->T
dijkstra(u,1,3); // direcionando todas as arestas do commuter pass de T->S
int resp=min(dist[v][0],dist[v][1]);
cout << ans << endl;
//assert(resp>=ans);
//cout << resp << endl;
return 0;
} // sub3