Submission #926789

#	Time	Username	Problem	Language	Result	Execution time	Memory
926789		haru09	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	241 ms	16088 KiB

commuter_pass

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define task "code"

const int ar=1e5+5;
const ll mod=1e9+7;
int n,m;
int s,t;
int u,v;
ll dp[2][ar];
vector<pair<int,int>> ad[ar];
vector<int> it;
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>> > pq;
ll dist[5][ar];
void dijkstra(int x,int t)
{
    for (int i=1;i<=n;i++) dist[t][i]=1e18;
    dist[t][x]=0;
    pq.push({0,x});
    while(pq.size())
    {
        pair<ll,int> top=pq.top();
        pq.pop();
        ll d=top.fi;
        int u=top.se;
        if (d>dist[t][u]) continue;
        for (auto [v,w]:ad[u])
        {
            ll val=dist[t][u]+w;
            if (val<dist[t][v])
            {
                dist[t][v]=val;
                pq.push({val,v});
            }
        }
    }
}
bool cmp(int x,int y)
{
    return dist[1][x]<dist[1][y];
}
ll ans=1e18;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    if (fopen(task".inp","r"))
    {
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin>>n>>m>>s>>t>>u>>v;
    for (int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        ad[a].push_back({b,c});
        ad[b].push_back({a,c});
    }
    dijkstra(s,1);
    dijkstra(t,2);
    dijkstra(u,3);
    dijkstra(v,4);
    for (int i=1;i<=n;i++) it.push_back(i);
    sort(it.begin(),it.end(),cmp);
    ans=dist[3][v];
    for (auto ver:it)
    {
        if (dist[1][ver]+dist[2][ver]!=dist[1][t]) continue;
        dp[0][ver]=dist[3][ver];
        dp[1][ver]=dist[4][ver];
        for (auto [p,w]:ad[ver])
        {
            if (dist[1][p]!=dist[1][ver]-w) continue;
            if (dist[1][p]+dist[2][p]!=dist[1][t]) continue;
            ans=min(ans,dist[3][ver]+dp[1][p]);
            ans=min(ans,dist[4][ver]+dp[0][p]);
            dp[0][ver]=min(dp[0][ver],dp[0][p]);
            dp[1][ver]=min(dp[1][ver],dp[1][p]);
        }
    }
    cout<<ans;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
commuter_pass.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 45 / 45