Submission #1175720

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()

template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, pll> P;

#define INF (1<<29)
#define INFL (1ll<<60)
#define EPS (1e-8)
#define PI (acos(-1))
const ll MOD = 1000000007ll;

struct Edge {
	int to, lastpos;
	ll cost, lastcost;
	
	
	Edge(int to, ll cost, int lastpos, ll lastcost)
	 : to(to), cost(cost), lastpos(lastpos), lastcost(lastcost) {}
};

int n, m;
int st, ed;
vector<Edge> g[26000];
int s[26000], w[26000];
ll sum[26000], d[26000];

int main() {
	cin >> n >> m >> st >> ed;
	REP(i, m) {
		int l;
		scanf("%d", &l);
		
		REP(j, l) scanf("%d", s + j);
		REP(j, l - 1) scanf("%d", w + j);
		
		sum[0] = 0;
		REP(j, l) sum[j + 1] = sum[j] + w[j];
		
		REP(j, l - 1) g[s[j]].push_back(Edge(s[j + 1], w[j], s[l - 1], sum[l - 1] - sum[j]));
		for (int j = l - 1; j > 0; j--) g[s[j]].push_back(Edge(s[j - 1], w[j - 1], s[0], sum[j] - sum[0]));
	}
	
	fill(d, d + n, INFL);
	
	priority_queue<P, vector<P>, greater<P> > pq;
	pq.push(P(1, pll(0, st)));
	
	while (!pq.empty()) {
		P now = pq.top(); pq.pop();
		
		ll over = -now.first;
		ll cost = now.second.first;
		int pos = now.second.second;
		
		if (over != -1 && !chmin(d[pos], cost + over * 2)) continue;
		
		REP(i, g[pos].size()) {
			Edge& e = g[pos][i];
			
			pq.push(P(- max(over, e.lastcost - e.cost), pll(cost + e.cost, e.to)));
			pq.push(P(0, pll(cost + e.lastcost, e.lastpos)));
		}
	}
	
	cout << d[ed] << endl;
	
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:41:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &l);
                  ^
./Main.cpp:43:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   REP(j, l) scanf("%d", s + j);
                               ^
./Main.cpp:44:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   REP(j, l - 1) scanf("%d", w + j);
                                   ^

Judge Result