Submission #1094247

#	Time	Username	Problem	Language	Result	Execution time	Memory
1094247		lamlamlam	Commuter Pass (JOI18_commuter_pass)	C++17	100 / 100	271 ms	61772 KiB

commuter_pass

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define pii pair<int,int>
const int MN = 2e5+5,inf = 1e18;
int n,m,a,b,c,d,u,v,w,dist[MN],dp[MN][4];
bool is_candidates[MN];
vector<int> trace[MN],g1[MN],g2[MN];
vector<pii> adj[MN];
void dickfather1(int x)
{
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    for(int i=0; i<MN; i++) dist[i] = inf;
    dist[x] = 0;
    pq.push({0,x});
    while(!pq.empty()){
        auto tmp = pq.top();
        pq.pop();
        int d = tmp.first;
        int u = tmp.second;
        if(d!=dist[u]) continue;
        for(auto y:adj[u]){
            int v = y.first;
            int len = y.second;
            if(d+len<dist[v]){
                trace[v].clear();
                trace[v].push_back(u);
                dist[v] = d+len;
                pq.push({dist[v],v});
            }
            else if(d+len==dist[v]) trace[v].push_back(u);
        }
    }
}
bool vis[MN];
void dfs(int x)
{
    is_candidates[x] = true;
    vis[x] = true;
    for(auto v:trace[x]) {
        if(!vis[v]) dfs(v);
        g1[x].push_back(v);
        g2[v].push_back(x);
    }
}
struct Data
{
    int d,v,phase;
    bool operator < (const Data &o) const
    {
        return d > o.d;
    }
};
void dickfather2(int st)
{
    for(int i=0; i<MN; i++) dp[i][0] = dp[i][1] = dp[i][2] = dp[i][3] = inf;
    priority_queue<Data> pq;
    dp[st][0] = 0;
    pq.push({0,st,0});
    while(!pq.empty())
    {
        auto tmp = pq.top();
        pq.pop();
        int d = tmp.d;
        int v = tmp.v;
        int phase = tmp.phase;
        if(d!=dp[v][phase]) continue;
        if(phase==0){
            for(auto e:adj[v]){
                int u = e.first;
                int len = e.second;
                if(d+len<dp[u][0]){
                    dp[u][0] = d + len;
                    pq.push({dp[u][0],u,0});
                }
            }
            for(auto u:g1[v]) {
                if(d<dp[u][1]){
                    dp[u][1] = d;
                    pq.push({dp[u][1],u,1});
                }
            }
            for(auto u:g2[v]) {
                if(d<dp[u][2]){
                    dp[u][2] = d;
                    pq.push({dp[u][2],u,2});
                }
            }
        }
        else if(phase==1){
            for(auto e:adj[v]){
                int u = e.first;
                int len = e.second;
                if(d+len<dp[u][3]){
                    dp[u][3] = d + len;
                    pq.push({dp[u][3],u,3});
                }
            }
            for(auto u:g1[v]) {
                if(d<dp[u][1]){
                    dp[u][1] = d;
                    pq.push({dp[u][1],u,1});
                }
            }
        }
        else if(phase==2){
            for(auto e:adj[v]){
                int u = e.first;
                int len = e.second;
                if(d+len<dp[u][3]){
                    dp[u][3] = d + len;
                    pq.push({dp[u][3],u,3});
                }
            }
            for(auto u:g2[v]) {
                if(d<dp[u][2]){
                    dp[u][2] = d;
                    pq.push({dp[u][2],u,2});
                }
            }
        }
        else{
            for(auto e:adj[v]){
                int u = e.first;
                int len = e.second;
                if(d+len<dp[u][3]){
                    dp[u][3] = d + len;
                    pq.push({dp[u][3],u,3});
                }
            }
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #define task "sus"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin >> n >> m >> a >> b >> c >> d;
    for(int i=1; i<=m; i++){
        cin >> u >> v >> w;
        adj[u].push_back({v,w});
        adj[v].push_back({u,w});
    }
    dickfather1(a);
    dfs(b);
    dickfather2(c);
    //for(int i=1; i<=n; i++) for(auto v:g2[i]) cout << i << ' ' << v << endl;
    cout << min({dp[d][0],dp[d][1],dp[d][2],dp[d][3]});
    cerr << "\nTime: " << clock() << endl;
}

Compilation message (stderr)

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

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