AOJ -2819 Country in Distortion
Country in Distortion | Aizu Online Judge
拡張Dijkstraの問題です。
各頂点に対して、頂点に到着した速度で次の辺へのコストが代わるので、今回はとして頂点からの距離を持ちます。
ここで注意しないと行けないのが、無向グラフかつコストが0の辺が存在するので、continueの条件式をとしなければ行けません。
具体的には
if(d[next.first][_v]<=now.first.first+next.second*v)continue; d[next.first][_v]=now.first.first+next.second*v; que.push(piii(pii(d[next.first][_v],next.first),_v));
ifの条件式の部分です。
今持っているコストで次の頂点へと推移できる。これをcontinueで弾かなければqueに無限にpushされることになります(REになってしまいます)
#include<bits/stdc++.h> #define int long long #define rep(i,n) for(int i=0; i<n;i++) using namespace std; #define MAX 1e9 int INF=MAX*MAX; typedef pair<int,int> pii; typedef pair<pii,long long> piii; vector<vector<long long>>d(501,vector<long long>(51,INF)); signed main(){ int n,m; cin>>n>>m; vector<vector<pii>>edge(n,vector<pii>()); rep(i,m){ int a,b,c; cin>>a>>b>>c; --a,--b; edge[a].push_back(pii(b,c)); edge[b].push_back(pii(a,c)); } int v0,a,b,c; cin>>v0>>a>>b>>c; priority_queue<piii,vector<piii>,greater<piii>>que; d[0][v0]=0; que.push(piii(pii(0,0),v0)); while(!que.empty()){ piii now=que.top(); que.pop(); int v=now.second; int _v=(v*a+b)%c; /*queに積んでる間に最短距離が更新されたかを防ぐifなので<で良い*/ if(d[now.first.second][v]<now.first.first)continue; for(int i=0; i<edge[now.first.second].size();i++){ pii next=edge[now.first.second][i]; if(d[next.first][_v]<=now.first.first+next.second*v)continue; d[next.first][_v]=now.first.first+next.second*v; que.push(piii(pii(d[next.first][_v],next.first),_v)); } } int ans=INF; rep(i,51)if(d[n-1][i]!=INF){ vector<vector<long long>>_d(501,vector<long long>(51,INF)); _d[n-1][i]=d[n-1][i]; que.push(piii(pii(d[n-1][i],n-1),i)); while(!que.empty()){ piii now=que.top(); que.pop(); int v=now.second; int _v=(v*a+b)%c; if(_d[now.first.second][v]<now.first.first)continue; for(int i=0; i<edge[now.first.second].size();i++){ pii next=edge[now.first.second][i]; if(_d[next.first][_v]<=now.first.first+next.second*v)continue; _d[next.first][_v]=now.first.first+next.second*v; que.push(piii(pii(_d[next.first][_v],next.first),_v)); } } rep(i,51)ans=min(ans,_d[0][i]); } cout<<ans<<endl; }