ここからちょっと配点の高い問題。
それでも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; }
まとめ
まだまだ簡単。