結果

問題 No.496 ワープクリスタル (給料日前編)
ユーザー vjudge1
提出日時 2025-03-14 17:52:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,944 bytes
コンパイル時間 2,156 ms
コンパイル使用メモリ 199,596 KB
実行使用メモリ 201,108 KB
最終ジャッジ日時 2025-03-14 17:52:44
合計ジャッジ時間 11,924 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 21 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
//#define int long long
using namespace std;
inline int read()
{
   int x=0,f=1;char ch=getchar();
   while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
   while (ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-48;ch=getchar();}
   return x*f;
}
void write(int x)
{
   if(x<0)putchar('-'),x=-x;
   if(x<10)putchar(x+'0');
   else write(x/10),putchar(x%10+'0');
}
const int N=2e6;
const int mod=1e9+7;
struct node{
	int u,v,w,nxt;
}mp[N*6];
int top;
int idx[N];
void add(int u,int v,int w){
	mp[++top]={u,v,w,idx[u]};
	idx[u]=top;
}
int X,Y,n,f;
int u[100],v[100],w[100];
int id(int a,int b){
	return (a-1)*105+b;
}
struct nd{
	int id,z;
	bool operator < (const nd &p)const{
		return z>p.z; 
	}
};
bool vis[N*6];
priority_queue<nd>q;
int dis[N*6];
void dij(){
	memset(dis,0x3f,sizeof dis);
	dis[1]=0;
	q.push((nd){1,0});
	while(!q.empty()) {
		nd now=q.top();
		q.pop();
		if(vis[now.id])continue;
		vis[now.id]=1;
		for(int i=idx[now.id];i;i=mp[i].nxt){
			int v=mp[i].v;
			if(dis[v]>dis[now.id]+mp[i].w){
				dis[v]=dis[now.id]+mp[i].w;
				q.push((nd){v,dis[v]});
			}
		}
	}
	int zd=id(X,Y);
	int ans=INT_MAX;
	for(int i=0;i<=n;i++)
	ans=min(ans,dis[zd+105*105*i]);
	cout<<ans<<"\n";
}
signed main(){
//	freopen("crystal.in","r",stdin);
//	freopen("crystal.out","w",stdout);
	X=read(),Y=read(),n=read(),f=read();
	X++;
	Y++; 
	int all=105*105;
	for(int i=1;i<=n;++i)u[i]=read(),v[i]=read(),w[i]=read();
	for(int i=1;i<=105;++i){
		for(int j=1;j<=105;j++){
			int dd=id(i,j);
			if(i+1<=105)
			add(dd,id(i+1,j),f);
			if(j+1<=105)
			add(dd,id(i,j+1),f);
			for(int k=1;k<=n;k++){
				if(i+u[k]<=105&&j+v[k]<=105) add(dd,id(i+u[k],j+v[k])+all*k,w[k]);
			//	add(dd,dd+all*k,w[k]);
				if(i+1<=105) 
				add(dd+all*k,id(i+1,j)+all*k,f);
				if(j+1<=105)
				add(dd+all*k,id(i,j+1)+all*k,f);
				for(int l=1;l<k;l++)if(i+u[k]<=105&&j+v[k]<=105)add(dd+all*l,id(i+u[k],j+v[k])+all*k,w[k]);
			}
		}
	}
	dij();
    return 0;
}
0