제출 #381255

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
381255		oleksg	Commuter Pass (JOI18_commuter_pass)	C++11	31 / 100	745 ms	42244 KiB

commuter_pass

#pragma GCC optimize("O2")
#include <fstream>
#include <string>
#include <iostream>
#include <bitset>
#include <math.h>
#include <string>
#include <algorithm>
#include <assert.h>
#include <bits/stdc++.h>
#include <vector>
#include <queue>
#include<stdio.h>
#include<ctype.h>
#define ll long long
using namespace std;

struct con{
    ll des;
    ll w;
};

ll n, m;

ll s, t;

ll u, v;

ll dist[100001];
ll used[100001];
ll used2[100001][2];
ll dist2[100001][2];
ll keep[100001];
// keep track of all the nodes going to us that can reach us in the minimum distance, later updated to only be nodes that go to us however we also gotta be a usable node that leads back to t
vector<ll> tous[100001];


vector<con> cons[100001];

vector<con> freeconsfor[100001];
vector<con> freeconsback[100001];

struct node{
    ll dist;
    ll cur;
    ll dir;
    bool operator<(const node& y) { return dist > y.dist; }
};

bool Compare(node a, node b)
{
    return a.dist > b.dist;
}

void dfs(int cur){
    keep[cur] = 1;
    for (auto it: tous[cur]){
        if (keep[it] == -1){
            keep[it] = 1;
            dfs(it);
        }
    }
}
int main(){
    cin >> n >> m >> s >> t >> u >> v;
    s -= 1;
    t -= 1;
    u -= 1;
    v -= 1;
    ll one, two, three;
    for (int x = 0; x < m; x++){
        cin >> one >> two >> three;
        cons[one - 1].push_back({two - 1, three});
        cons[two - 1].push_back({one - 1, three});
    }
    for (int x = 0; x < n; x++){
        dist[x] = 1e15;
        used[x] = -1;
        keep[x] = -1;
    }
    priority_queue<pair<ll, ll>> q;
    dist[s] = 0;
    q.push({0, s});
    while(q.size() > 0){
        ll curdist = q.top().first * -1;
        ll cur = q.top().second;
        q.pop();
        if (used[cur] == -1){
            used[cur] = 1;
            for (auto next: cons[cur]){
                if (dist[next.des] > dist[cur] + next.w){
                    dist[next.des] = dist[cur] + next.w;
                    tous[next.des].clear();
                    tous[next.des].push_back(cur);
                    q.push({-1*dist[next.des], next.des});
                }
                else if (dist[next.des] == dist[cur] + next.w){
                    //partial update
                    tous[next.des].push_back(cur);
                }
            }
        }
    }
    dfs(t);
    for (int x = 0; x < n; x++){
        if (keep[x] == 1){
            for (auto it: tous[x]){
                freeconsfor[x].push_back({it, 0});
                freeconsback[it].push_back({x, 0});
                //cout << x << " " << it << " " << "free\n";
            }
        }
    }
    //dijkstra part 2, this time we know what the free cons are
    priority_queue<node, vector<node>, function<bool(node a, node b)>> qs(Compare);
    for (int x = 0; x < n; x++){
        dist2[x][0] = 1e15;
        dist2[x][1] = 1e15;
        used2[x][0] = -1;
        used2[x][1] = -1;
    }
    qs.push({0, u, 0});
    qs.push({0, u, 1});
    dist2[u][0] = 0;
    dist2[u][1] = 0;
    while(qs.size() > 0){
        ll curdist = qs.top().dist;
        ll cur = qs.top().cur;
        ll dir = qs.top().dir;
        qs.pop();
        if (used2[cur][dir] == -1){
            used2[cur][dir] = 1;
            //cout << "yes\n";
            for (auto next: cons[cur]){
                if (dist2[next.des][dir] > dist2[cur][dir] + next.w){
                    dist2[next.des][dir] = dist2[cur][dir] + next.w;
                    qs.push({dist2[next.des][dir], next.des, dir});
                }
            }
            if (dir == 0){
                for (auto next: freeconsfor[cur]){
                    if (dist2[next.des][dir] > dist2[cur][dir] + next.w){
                        dist2[next.des][dir] = dist2[cur][dir] + next.w;
                        qs.push({dist2[next.des][dir], next.des, dir});
                    }
                }
            }
            else{
                for (auto next: freeconsback[cur]){
                    if (dist2[next.des][dir] > dist2[cur][dir] + next.w){
                        dist2[next.des][dir] = dist2[cur][dir] + next.w;
                        qs.push({dist2[next.des][dir], next.des, dir});
                    }
                }
            }
        }
    }
    cout << min(dist2[v][0], dist2[v][1]) << "\n";

}

컴파일 시 표준 에러 (stderr) 메시지

commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:85:12: warning: unused variable 'curdist' [-Wunused-variable]
   85 |         ll curdist = q.top().first * -1;
      |            ^~~~~~~
commuter_pass.cpp:127:12: warning: unused variable 'curdist' [-Wunused-variable]
  127 |         ll curdist = qs.top().dist;
      |            ^~~~~~~

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