2013-12-16

■ JOI予選 17:00

1 足し算と割り算

2 貪欲...っていうのかこれ

3 数式一本でできるJOI予選には珍しい問題

4 BitDP

5 Dijkstra

6 順序を状態にもつDP

らしいです。

自分はおそらく440点でした。本選ではもう少しちゃんとした結果を残したいです。

(以下自戒の意味を込めて)

5番(20点のコード)

//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
//Prob 5
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
int c[5005],r[5005];
vector<int>edge[5005];
int d[5005][5005];
int n,k;
void dijkstra()
{
	priority_queue,greater >que;
	d[1][r[1]]=c[1];
	que.push(mp(c[1],mp(1,r[1])));
	
	while(!que.empty())
	{
		P1 p=que.top(); que.pop();
		int cur=p.first;
		int v=p.second.first;
		int zan=p.second.second;
		if(cur!=d[v][zan]) continue;
		for(int i=0;iint ne=edge[v][i];
			if(zan-1if(d[ne][r[ne]]>d[v][zan]+c[ne])
				{
					d[ne][r[ne]]=d[v][zan]+c[ne];
					que.push(mp(d[ne][r[ne]],mp(ne,r[ne])));
				}
			}
			
			if(zan>=1)
			{
				if(d[ne][zan-1]>d[v][zan])
				{
					d[ne][zan-1]=d[v][zan];
					que.push(mp(d[ne][zan-1],mp(ne,zan-1)));
				}
			}
		}
	}
	int ret=INF;
	for(int j=0;j<5005;j++)
	{
		ret=min(ret,d[n][j]);
	}
	printf("%d\n",ret);
}
int main(){
	scanf("%d %d",&n,&k);
	
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d",&c[i],&r[i]);
	}
	for(int i=0;iint a,b;
		scanf("%d %d",&a,&b);
		edge[a].pb(b);
		edge[b].pb(a);
	}
	for(int i=0;i<5005;i++)for(int j=0;j<5005;j++)d[i][j]=2e8;
	dijkstra();
	return 0;
}

5番(100点のコード)

//Bokan ga bokka--nn!!
//Daily Lunch Special Tanoshii !!
//Prob 5
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
int c[5005],r[5005];
vector<int>edge[5005];
int d[5005][5005];
int n,k;
void dijkstra()
{
	priority_queue,greater >que;
	d[1][r[1]]=c[1];
	que.push(mp(c[1],mp(1,r[1])));
	
	while(!que.empty())
	{
		P1 p=que.top(); que.pop();
		int cur=p.first;
		int v=p.second.first;
		int zan=p.second.second;
		if(cur!=d[v][zan]) continue;
		for(int i=0;iint ne=edge[v][i];
	/*ここです*/	if(zan>=1&&zan-1if(d[ne][r[ne]]>d[v][zan]+c[ne])
				{
					d[ne][r[ne]]=d[v][zan]+c[ne];
					que.push(mp(d[ne][r[ne]],mp(ne,r[ne])));
				}
			}
			
			if(zan>=1)
			{
				if(d[ne][zan-1]>d[v][zan])
				{
					d[ne][zan-1]=d[v][zan];
					que.push(mp(d[ne][zan-1],mp(ne,zan-1)));
				}
			}
		}
	}
	int ret=INF;
	for(int j=0;j<5005;j++)
	{
		ret=min(ret,d[n][j]);
	}
	printf("%d\n",ret);
}
int main(){
	scanf("%d %d",&n,&k);
	
	for(int i=1;i<=n;i++)
	{
		scanf("%d %d",&c[i],&r[i]);
	}
	for(int i=0;iint a,b;
		scanf("%d %d",&a,&b);
		edge[a].pb(b);
		edge[b].pb(a);
	}
	for(int i=0;i<5005;i++)for(int j=0;j<5005;j++)d[i][j]=2e8;
	dijkstra();
	return 0;
}

ツイートする