Submission #617804

---

Source Code Expand

    #include <cstdio>
    #include <vector>
    #include <queue>
    #include <utility>
    using namespace std;
    vector<int> v[26000];
    int nxt[260000][2];
    int len[260000][2];
    int over[260000][2], olen[260000][2];
    int s[260000], w[260000];
    long long d[26000], dt[26000];
    int src, dst, n;
    int f(long long mid) {
    	priority_queue<pair<long long, int> > q;
    	q.push(make_pair(0, src));
    	for (int i = 0; i < n; i++) {
    		dt[i] = 1ll << 61;
    	}
    	dt[src] = 0;
    	while (q.size()) {
    		int pos = q.top().second;
    		long long dis = -q.top().first;
    		q.pop();
    		if (dis != dt[pos]) continue;
    		for (int i = 0; i < v[pos].size(); i++) {
    			int en = v[pos][i];
    			for (int j = 0; j < 2; j++) {
    				if (nxt[en][j] == -1) continue;
    				int npos = nxt[en][j];
    				long long ndis = dis + len[en][j];
    				long long odis = dis + olen[en][j];
    				int opos = over[en][j];
    				if (odis + d[opos] <= mid && dt[npos] > ndis) {
    					dt[npos] = ndis;
    					q.push(make_pair(-ndis, npos));
    				}
    			}
    		}
    	}
    	return dt[dst] <= mid;
    }
    int main() {
    	int m;
    	scanf("%d%d%d%d", &n, &m, &src, &dst);
    	int mc = 0;
    	for (int i = 0; i < m; i++) {
    		int l;
    		scanf("%d", &l);
    		for (int j = 0; j < l; j++) {
    			scanf("%d", &s[j]);
    		}
    		int W = 0;
    		for (int j = 0; j < l - 1; j++) {
    			scanf("%d", &w[j]);
    			W += w[j];
    		}
    		int ww = 0;
    		for (int j = 0; j < l; j++) {
    			int x = s[j];
    			nxt[mc][0] = nxt[mc][1] = -1;
    			if (j > 0) {
    				nxt[mc][0] = s[j-1];
    				len[mc][0] = w[j-1];
    				over[mc][0] = s[0];
    				olen[mc][0] = ww;
    			}
    			if (j < l - 1) {
    				nxt[mc][1] = s[j+1];
    				len[mc][1] = w[j];
    				over[mc][1] = s[l-1];
    				olen[mc][1] = W - ww;
    			}
    			v[x].push_back(mc);
    			mc++;
    			ww += w[j];
    		}
    	}
    	for (int i = 0; i < n; i++) {
    		d[i] = 1ll << 61;
    	}
    	priority_queue<pair<long long, int> > q;
    	q.push(make_pair(0, dst));
    	d[dst] = 0;
    	while (q.size()) {
    		int pos = q.top().second;
    		long long dis = -q.top().first;
    		q.pop();
    		if (dis != d[pos]) continue;
    		for (int i = 0; i < v[pos].size(); i++) {
    			int en = v[pos][i];
    			for (int j = 0; j < 2; j++) {
    				if (nxt[en][j] == -1) continue;
    				int npos = nxt[en][j];
    				long long ndis = dis + len[en][j];
    				if (d[npos] > ndis) {
    					d[npos] = ndis;
    					q.push(make_pair(-ndis, npos));
    				}
    			}
    		}
    	}
    	long long lo = 0, hi = 1ll << 60;
    	while (lo + 1 < hi) {
    		long long mid = (lo + hi) / 2;
    		if (f(mid)) {
    			hi = mid;
    		} else {
    			lo = mid;
    		}
    	}
    	printf("%lld\n", hi);
    	return 0;
    }

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:44:43: 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:48:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &l);
                      ^
./Main.cpp:50:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
        scanf("%d", &s[j]);
                          ^
./Main.cpp:54:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
        scanf("%d", &w[j]);
                          ^

Judge Result