제출 #1087633

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1087633		FubuGold	Commuter Pass (JOI18_commuter_pass)	C++14	100 / 100	200 ms	24140 KiB

commuter_pass

#include <bits/stdc++.h>

using namespace std;

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

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

long long dis[4][MAXN+2];
vector<Edge> adj[MAXN+2];
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_w = -pq.top().first;
        pq.pop();
        if (cur_w > dis[id][u]) continue;
        for (int i=0;i<adj[u].size();i++) {
            int v = adj[u][i].v;
            int w = adj[u][i].w;
            if (dis[id][v] > cur_w + w) {
                dis[id][v] = cur_w + w;
                pq.push(make_pair(-dis[id][v],v));
            }
        }
    }
}

bool vst[MAXN+2];
int topo_pos[MAXN+2];
int topo[MAXN+2];
int sz = 0;
void dfs(int u) {
    vst[u] = 1;
    for (int i=0;i<adj[u].size();i++) {
        if (adj[u][i].in == 0) continue;
        int v = adj[u][i].v;
        if (vst[v]) continue;
        dfs(v);
    }
    topo[++sz] = u;
}

long long dp[2][MAXN+2];

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 short_s_t = 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;
            int w = adj[u][i].w;
            if (dis[0][u] + dis[1][v] + w == short_s_t) {
                adj[u][i].in = 1;
            }
        }
    }

    dfs(s);
    reverse(topo+1,topo+sz+1);
    for (int i=1;i<=sz;i++) {
        topo_pos[topo[i]] = i;
        dp[0][i] = dp[1][i] = LL_INF;
    }
//    cout << short_s_t << ' ' << ans << '\n';
    for (int i=1;i<=sz;i++) {
        int u = topo[i];
//        cerr << u << ' ' << i << '\n';
        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 id = topo_pos[v];
            dp[0][id] = min(dp[0][id], dp[0][i]);
            dp[1][id] = min(dp[1][id], dp[1][i]);
        }
    }
    cout << ans;
    return 0;
}

컴파일 시 표준 에러 (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:47:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i=0;i<adj[u].size();i++) {
      |                  ~^~~~~~~~~~~~~~
commuter_pass.cpp: In function 'int main()':
commuter_pass.cpp:75:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (int i=0;i<adj[u].size();i++) {
      |                      ~^~~~~~~~~~~~~~
commuter_pass.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         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