Submission #1086644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1086644		FubuGold	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	253 ms	27564 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 200000;
const long long LL_INF = 1000000000ll * 1000000000;

struct Edge {
    int v,w;
    bool in;
    Edge() {};
    Edge(int _v,int _w,bool _in) : v(_v), w(_w), in(_in) {};
};

vector<Edge> adj[MAXN+1];
long long dis[4][MAXN+1];
int n,m;
int s,t,l,r;

void dijkstra(int st,int id) {
    for (int i=1;i<=n;i++) dis[id][i] = LL_INF;
    dis[id][st] = 0;
    priority_queue<pair<long long,int>> pq;
    pq.push(make_pair(0,st));
    while (pq.size()) {
        int u = pq.top().second;
        long long cur_d = -pq.top().first;
        pq.pop();
        if (cur_d > dis[id][u]) continue;
        for (int i=0;i<adj[u].size();i++) {
            int v = adj[u][i].v, w = adj[u][i].w;
            if (dis[id][v] > cur_d + w) {
                dis[id][v] = cur_d + w;
                pq.push(make_pair(-dis[id][v],v));
            }
        }
    }
}

vector<int> topo;
int pos_topo[MAXN+1];
int vst[MAXN+2];
long long dp[2][MAXN+1];
void dfs(int u) {
    vst[u] = 1;
    for (int i=0;i<adj[u].size();i++) {
        if (!adj[u][i].in) continue;
        int v = adj[u][i].v;
        if (!vst[v]) dfs(v);
    }
    topo.push_back(u);
}

int main() {
    cin.tie(0) -> sync_with_stdio(0);
    cin >> n >> m;
    cin >> s >> t >> l >> r;
    for (int i=1;i<=m;i++) {
        int x,y,w; cin >> x >> y >> w;
        adj[x].push_back(Edge(y,w,0));
        adj[y].push_back(Edge(x,w,0));
    }
    dijkstra(s,0);
    dijkstra(t,1);
    dijkstra(l,2);
    dijkstra(r,3);
    long long shortest = dis[0][t];
    long long ans = dis[2][r];
    for (int u=1;u<=n;u++) {
        for (int i=0;i<adj[u].size();i++) {
            int v = adj[u][i].v, w = adj[u][i].w;
            if (dis[0][u] + dis[1][v] + w == shortest) {
                adj[u][i].in = 1;
            }
        }
    }
    dfs(s);
    topo.push_back(0);
    reverse(topo.begin(),topo.end());
    for (int i=1;i<topo.size();i++) {
        pos_topo[topo[i]] = i;
        dp[0][i] = dp[1][i] = LL_INF;
    }
    dp[0][1] = dis[2][topo[1]];
    dp[1][1] = dis[3][topo[1]];
    for (int i=1;i<topo.size();i++){
        int u = topo[i];

        dp[0][i] = min(dp[0][i], dis[2][u]);
        dp[1][i] = min(dp[1][i], dis[3][u]);

        ans = min(ans,dp[0][i] + dis[3][u]);
        ans = min(ans,dp[1][i] + dis[2][u]);

        for (int j=0;j<adj[u].size();j++) {
            if (!adj[u][j].in) continue;
            int v = adj[u][j].v;
            int pos_v = pos_topo[v];
            dp[0][pos_v] = min({dp[0][pos_v],dp[0][i]});
            dp[1][pos_v] = min({dp[1][pos_v],dp[1][i]});
        }
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

commuter_pass.cpp: In function 'void dijkstra(int, int)':
commuter_pass.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int i=0;i<adj[u].size();i++) {
      |                      ~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'void dfs(int)':
commuter_pass.cpp:46:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for (int i=0;i<adj[u].size();i++) {
      |                  ~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:70:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |         for (int i=0;i<adj[u].size();i++) {
      |                      ~^~~~~~~~~~~~~~
commuter_pass.cpp:80:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for (int i=1;i<topo.size();i++) {
      |                  ~^~~~~~~~~~~~
commuter_pass.cpp:86:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i=1;i<topo.size();i++){
      |                  ~^~~~~~~~~~~~
commuter_pass.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         for (int j=0;j<adj[u].size();j++) {
      |                      ~^~~~~~~~~~~~~~

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