NOIP 2017 Day 1題3:公園をぶらぶらする最短経路+ダイナミックプランニング
analysis
これはAK問題だと言われていますか?いいえ、そうではありません.
まず隣接テーブルで保存しながらspfaを1回走り、dis[i]は1からiの最短距離を表す(spfaができないとは言わないでください) f[i][j]を1からiまでのすべてのパスのうちdis[n]より大きいKを表すパス数とする だからある
f[i][j]=∑f[k][dis[i]−dis[k]+j−len[i][k]]
これを見て、あなたは
DP
?
メモリー検索!
我々は
n
スタート
逆検索
とします.
dis[i]−dis[k]+j−len[i][k]＜0
もちろん検索はしません
では、私たちの最大の敵である判0環は? f[x][y]という状態が1回のdfsに2回現れると、それは0リングがあり、returnがいいので、配列をつけてマークします.
finally
ans=(∑i=0nf[n][i])modp
彼のコード.書いています.....すでに7組のデータが通過し,0ループはまだ研究されている.
/*
1
5 10 0 595078320
1 2 1
2 5 1
2 1 2
5 2 1
2 3 1
3 5 1
1 5 2
4 1 1
3 1 2
4 2 1
2
：4 */
#include
using namespace std;
const int MAX_N=100001;
struct edge{
int to;
int cost;
};
vector G[MAX_N];
vector ReG[MAX_N];
int dis[MAX_N];
int N,M,K,pmod;
int dp[MAX_N][51];
bool roll;
void input(){
for(int i=0;i> N >> M >> K >> pmod;
for(int i=1;i<=M;i++){
int a,b,c; cin >> a >> b>>c;
G[a].push_back( (edge){b,c} );
ReG[b].push_back( (edge){a,c} );
}
memset(dp, 0 ,sizeof(dp));
dp[1][0]=1;
fill(dis ,dis+N+1, 200000000);
roll=false;
}
int dfs(int v,int k){
if(dp[v][k]!=0) return dp[v][k];
//used[v]=true;
for( int j=0; j P;
priority_queue,greater
> que;
dis[1] = 0;
que.push( P(0,1));
while( !que.empty()){
P p = que.top(); que.pop();
int v= p.second;
if( dis[v] < p.first ) continue;
for( int i=0 ; i dis[v] + e.cost ){
dis[e.to] = dis[v] + e.cost;
que.push( P( dis[e.to] , e.to ));
}
}
}
}
int main() {
//freopen("park.in","r",stdin);
//freopen("park.out","w",stdout);
int T;cin>>T;
while(T--){
input();
dijkstra();
int ans=0;
for(int i=0;i<=K; i++){
ans = ( ans + dfs(N,i) ) % pmod;
}
//if(roll) cout << -1 <
NOIP 2017パーク巡り ダイナミックプランニング!
http://blog.csdn.net/qq_38678604/article/details/78572603#t4 この1編はよく書けている
https://www.cnblogs.com/CQzhangyu/p/7825839.html
https://www.cnblogs.com/Dndlns/p/7895996.html
//#define debug
#include
using namespace std;
const int MAX_N=1000001;
struct edge{
int to;
int cost;
};
vector G[MAX_N];
// vector ReG[MAX_N];
long long dis[MAX_N]; //
int N,M,K,pmod;
// bool used[MAX_N];
//int rudu[MAX_N] ; //
int dp[MAX_N][51];
vector O[MAX_N]; //
vector RO[MAX_N]; //
void input(){
cin >> N >> M >> K >> pmod;
for(int i=1;i<=M;i++){
int a,b,c; cin >> a >> b>>c;
G[a].push_back( (edge){b,c} );
// rudu[b]++;
//ReG[b].push_back( (edge){a,c});
if( c==0) {
O[a].push_back( (edge){b,c} ) ;
RO[b].push_back( (edge){a,c} ) ;
}
}
memset(dp, 0 ,sizeof(dp));
dp[1][0]=1;
fill(dis ,dis+N+1, 2000);
// for(int i=1;i<=M;i++){
//
// for( int j=0;j vs ; //
bool atO[MAX_N];
void dfs(int v){
used[v]=true;
for( int j=0; j=0 ;i--){
//for(int i=0; i P;
priority_queue,greater
> que;
dis[1] = 0;
que.push( P(0,1));
while( !que.empty()){
P p = que.top(); que.pop();
int v= p.second;
if( dis[v] < p.first ) continue;
for( int i=0 ; i dis[v] + e.cost ){
dis[e.to] = dis[v] + e.cost;
que.push( P( dis[e.to] , e.to ));
}
}
}
#ifdef debug
cout< qq;
qq.push(1);
us[1]=true;
while(!qq.empty()){
int s=qq.front(); qq.pop();
if( roll::atO[s] ) { return -1; }
for( int j=0; j < G[s].size(); j++){
edge e = G[s][j];
if( e.cost + dis[s] - dis[e.to] > K || e.cost + dis[s] - dis[e.to]<0 ) continue;// ！！
else
if( !us[e.to]) { qq.push(e.to) ; us[e.to] =true; };
for(int k=0; k<=K; k++){
int kk = k + e.cost + dis[s] - dis[e.to] ;
if( (kk>=0) && (kk <= K) ){
dp[e.to][ kk ] = ( dp[e.to][ kk ] + dp[s ][ k ] );
#ifdef debug
cout << "from " <>t;
while(t--){
input();
dijkstra();
roll::scc();
if( BFS()==-1 ) cout << -1;
else{
int ans = 0;
for(int i=0;i<=K; i++){
// cout <