kmjp's blog

競技プログラミング参加記です

QUPC2014 : D - 切符分割

ここからちょっと配点の高い問題。
それでもDiv1Easy~Div2Hard位の問題だけどね。
http://qupc2014.contest.atcoder.jp/tasks/qupc2014_d

問題

駅同士の路線及びその長さが与えられる。
また、価格表として距離と価格の対応が与えられる。

S駅からG駅に行く場合、切符を最大2枚買うことができる。
S駅からG駅に至る最安価格を求めよ。

解法

S駅から各駅、およびG駅から各駅への距離および価格をDijkstraで求める。
後は各駅Tを総当たりでチェックし、(S→T)と(T→G)の合計価格が最安なものを選べばよい。
また、切符1枚で(S→G)が最安ならそれを選ぶ。

int N,M,K;
int S,G;
vector<pair<int,int> > E[30001];
int dist[2][30001];
int cost[2][30001];
int X[102],F[102];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N>>M>>K;
	cin>>S>>G;
	FOR(i,M) {
		cin>>x>>y>>j;
		E[x].push_back(make_pair(y,j));
		E[y].push_back(make_pair(x,j));
	}
	FOR(i,K) cin>>X[i]>>F[i];
	X[K]=(1<<30)+1;
	K++;
	
	FOR(i,2) {
		FOR(j,N) dist[i][j]=1<<30;
		set<pair<int,int> > Q;
		if(i==0) dist[0][S]=0,Q.insert(make_pair(0,S));
		if(i==1) dist[1][G]=0,Q.insert(make_pair(0,G));
		
		while(!Q.empty()) {
			int co=Q.begin()->first;
			int cur=Q.begin()->second;
			Q.erase(Q.begin());
			if(co!=dist[i][cur]) continue;
			
			FOR(j,E[cur].size()) {
				int tar=E[cur][j].first;
				if(dist[i][tar]<=co+E[cur][j].second) continue;
				dist[i][tar] = co+E[cur][j].second;
				Q.insert(make_pair(dist[i][tar],tar));
			}
		}
		
		FOR(j,N) {
			FOR(k,K) if(dist[i][j]<X[k+1]) break;
			cost[i][j]=F[k];
		}
	}
	
	int mi=cost[0][G];
	FOR(j,N) mi=min(mi,cost[0][j]+cost[1][j]);
	cout<<mi<<endl;
}

まとめ

まだまだ簡単。