Submission #2978431

---

Source Code Expand

#include <cstdint>
#include <cstdio>
#include <set>
#include <vector>
#include <queue>

const int N = 1e5 + 10;
const int64_t INF = ~0ull >> 3;

int n, m, s, t;
std::vector<std::pair<int, int64_t>> e[N];

int id1[N];
int64_t d1[N], d2[N];
std::queue<std::pair<int, int>> q1;
bool in[N];

void spfa1() {
    in[t] = true;
    for (int i = 1; i <= n; i++)
        d1[i] = d2[i] = INF;
    d1[t] = d2[t] = 0;
    q1.emplace(t, -1);

    while (!q1.empty()) {
        static int u, from;
        u = q1.front().first;
        from = q1.front().second;
        in[u] = false;
        q1.pop();

        for (auto p : e[u]) {
            int64_t res = (id1[u] == p.first ? d2[u] : d1[u]) + p.second;
            if (res < d1[p.first]) {
                if (id1[p.first] != u) {
                    d2[p.first] = d1[p.first];
                    //printf("update2 %d %lld\n", p.first, d1[p.first]);
                }
                //printf("update1 %d %d %lld\n", p.first, u, d1[u] + p.second);
                id1[p.first] = u;
                d1[p.first] = res;
                if (!in[p.first]) {
                    in[p.first] = true;
                    q1.emplace(p.first, u);
                }
            } else if (id1[p.first] != u && res < d2[p.first]) {
                d2[p.first] = res;
                if (!in[p.first]) {
                    in[p.first] = true;
                    q1.emplace(p.first, u);
                }
                //printf("update %d %d %d %d\n", p.first, u, d1[u], p.second);
            }
        }
    }
}

int64_t v[N];
std::queue<int> q;

void spfa2() {
    in[t] = true;
    for (int i = 1; i <= n; i++)
        v[i] = INF;
    v[t] = 0;
    q.push(t);

    while (!q.empty()) {
        static int u;
        u = q.front();
        in[u] = false;
        q.pop();

        for (auto p : e[u]) {
            int64_t res = std::max(u == id1[p.first] ? d2[p.first] : d1[p.first], v[u] + p.second);
            if (res < v[p.first]) {
                v[p.first] = res;
                if (!in[p.first]) {
                    in[p.first] = true;
                    q.push(p.first);
                }
            }
        }
    }
}

int main() {
    scanf("%d%d%d%d", &n, &m, &s, &t);
    for (int i = 1; i <= m; i++) {
        static int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        e[u].emplace_back(v, w);
        e[v].emplace_back(u, w);
    }

    spfa1();
    spfa2();

    // for (int i = 1; i <= n; i++)
        // printf("%lld %lld %lld\n", id1[i], d1[i], d2[i]);

    if (v[s] == INF)
        puts("-1");
    else
        printf("%lld\n", v[s]);

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:105:30: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int64_t {aka long int}’ [-Wformat=]
         printf("%lld\n", v[s]);
                              ^
./Main.cpp:88:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &m, &s, &t);
                                      ^
./Main.cpp:91:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &u, &v, &w);
                                    ^

Judge Result