Submission #618178

---

Source Code Expand

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;

#define INF 1000000000

typedef pair<int, int> Pair;

struct Edge {
    int to;
    int len;
    int penalty;
    int last;
};

int n;
int m;
int low, high;
int src;
int dst;
struct Edge e[2][300000];
vector<Edge> es[30000];
int mind[30000];
int dist[30000];

void dijkstra(int s) {
    priority_queue<Pair, vector<Pair>, greater<Pair> > q;

    fill(mind, mind+n, INF);
    mind[s] = 0;
    q.push(Pair(0, s));
    while (!q.empty()) {
        Pair p = q.top(); q.pop();
        int cost = p.first;
        int idx = p.second;

        if (mind[idx] < cost) continue;
        for (int i=0; i<es[idx].size(); i++) {
            Edge &e = es[idx][i];
            int u = e.to;
            int len = e.len;

            if (mind[u] > cost + len) {
                mind[u] = cost + len;
                q.push(Pair(mind[u], u));
            }
        }
    }
}

bool check(int x) {
    priority_queue<Pair, vector<Pair>, greater<Pair> > q;

    fill(dist, dist+n, INF);
    dist[src] = 0;
    q.push(Pair(0, src));
    while (!q.empty()) {
        Pair p = q.top(); q.pop();
        int cost = p.first;
        int idx = p.second;

        if (dist[idx] < cost) continue;
        for (int i=0; i<es[idx].size(); i++) {
            Edge &e = es[idx][i];
            int u = e.to;
            int len = e.len;
            int penalty = e.penalty;
            int last = e.last;

            if (dist[u] > cost + len && cost+penalty<= x-mind[last]) {
                dist[u] = cost + len;
                q.push(Pair(dist[u], u));
            }
        }
    }
    return dist[dst] <= x;
}

int main() {
    scanf("%d%d%d%d", &n, &m, &src, &dst);
    for (int i=0; i<m; i++) {
        int l;
        int s, s2;

        scanf("%d", &l);
        scanf("%d", &s);
        e[1][l-2].to = s;
        for (int j=0; j<l-1; j++) {
            scanf("%d", &e[0][j].to);
            if (j < l-2) e[1][l-3-j].to = e[0][j].to;
            else s2 = e[0][j].to;
        }

        for (int j=0; j<l-1; j++) {
            scanf("%d", &e[0][j].len);
            e[1][l-2-j].len = e[0][j].len;
            e[0][j].last = s2;
            e[1][j].last = s;
        }

        e[0][l-1].penalty = 0;
        e[1][l-1].penalty = 0;
        for (int j=l-2; j>=0; j--) {
            e[0][j].penalty = e[0][j+1].penalty + e[0][j].len;
            e[1][j].penalty = e[1][j+1].penalty + e[1][j].len;
        }

        es[s].push_back(e[0][0]);
        es[s2].push_back(e[1][0]);
        for (int j=1; j<l-1; j++) {
            es[e[0][j-1].to].push_back(e[0][j]);
            es[e[1][j-1].to].push_back(e[1][j]);
        }
    }

    dijkstra(dst);
    low = mind[src]-1;
    high = INF;
    while (high - low > 1) {
        int mid = (high+low)/2;
        if (check(mid)) high = mid;
        else low = mid;
    }

    printf("%d\n", high);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:83:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d", &n, &m, &src, &dst);
                                          ^
./Main.cpp:88:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &l);
                        ^
./Main.cpp:89:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &s);
                        ^
./Main.cpp:92:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &e[0][j].to);
                                     ^
./Main.cpp:98:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_...

Judge Result