SRM 615 DIV1 Middle - LongLongTripDiv1 （復習×）
問題
Ｎ個の都市が存在する。
ある都市A[i]とB[i]を結ぶコストD[i]があらかじめわかっている。
このとき、都市0から都市N-1までちょうどコストTで移動できれば"Possible"、移動できなければ"Impossible"を返す。
解き方
D[i]は最大10000、Tは10^18のため単純な全探索はできない。
都市0からN-1まではどの経路を重複してもよいので、それぞれの場合を求めなければいけない。
このあたりで引っかかってしまったのでEditorialを読む。
ｄｐとしてTはそのまま扱えないが、０から直接つながる経路は最初に何回往復してもよいので、
その経路の往復分の距離ｄを考える。
ここで各都市について「都市番号」、「現在までのコスト%d」の状態を持つｄｐを考えることができる。
ここでｄｐの値はトータルのコストとなる。
最後に、dp[n-1][T%d]の値がＴ以下であれば、
都市Ｎ－１にＴ％ｄのコストで到達できることがわかるので、
ｄを足りない分だけ最初に往復すればちょうどＴで到達できるかを判定できる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
long long dist[60][20001];
class LongLongTripDiv1 {
public: string isAble(int N, vector<int> A, vector<int> B, vector<int> D, long long T) {
int n=A.size();
vector<pair<int,int> > p[60];
FORE(i,0,N)p[i].clear();
FORE(i,0,n){
p[A[i]].push_back(make_pair(B[i],D[i]));
p[B[i]].push_back(make_pair(A[i],D[i]));
}
if(p[0].empty())return "Impossible";
int d=2*p[0][0].second;
FORE(i,0,N)FORE(j,0,20001)dist[i][j]=T+1;
queue<pair<int,long long> > q;
q.push(make_pair(0,0));
dist[0][0]=0;
while(!q.empty()){
int x=q.front().first;
long long cost=q.front().second;
q.pop();
FORE(i,0,p[x].size()){
int next=p[x][i].first;
long long nextcost=p[x][i].second+cost;
if(nextcost>T)continue;
if(dist[next][nextcost%d]>nextcost){
dist[next][nextcost%d]=nextcost;
q.push(make_pair(next,nextcost));
}
}
}
return dist[N-1][T%d]<=T ? "Possible" : "Impossible";
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
long long dist[60][20001];
class LongLongTripDiv1 {
public: string isAble(int N, vector<int> A, vector<int> B, vector<int> D, long long T) {
int n=A.size();
vector<pair<int,int> > p[60];
FORE(i,0,N)p[i].clear();
FORE(i,0,n){
p[A[i]].push_back(make_pair(B[i],D[i]));
p[B[i]].push_back(make_pair(A[i],D[i]));
}
if(p[0].empty())return "Impossible";
int d=2*p[0][0].second;
FORE(i,0,N)FORE(j,0,20001)dist[i][j]=T+1;
queue<pair<int,long long> > q;
q.push(make_pair(0,0));
dist[0][0]=0;
while(!q.empty()){
int x=q.front().first;
long long cost=q.front().second;
q.pop();
FORE(i,0,p[x].size()){
int next=p[x][i].first;
long long nextcost=p[x][i].second+cost;
if(nextcost>T)continue;
if(dist[next][nextcost%d]>nextcost){
dist[next][nextcost%d]=nextcost;
q.push(make_pair(next,nextcost));
}
}
}
return dist[N-1][T%d]<=T ? "Possible" : "Impossible";
}
};
