已AC求助
查看原帖
已AC求助
315205
Kniqht楼主2023/11/3 07:46

这个代码95pts(宏定义了int=ll),而且是输出-1的点寄了,但是删去宏定义改一下%lld->%d就A了为啥捏

谢谢大佬

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e4+10,M=110,inf=0x3f3f3f3f;
int n,m,k;
int dist[N][M];
bool st[N][M]; 
//dist(i,j),st(i,j)到达i点,此时走的路程%k=j
//因为我们从起点出发后,只要求起点与终点的时间差是k的倍数
int h[N],e[N],ne[N],idx,TT[N];
void add(int a,int b,int c){
	e[idx]=b,ne[idx]=h[a],TT[idx]=c,h[a]=idx++;
}
struct Nd{
	int u,i,nw_t;
	bool operator<(const Nd &f)const{
		return nw_t>f.nw_t;
	}
};
signed main(){
	memset(h,-1,sizeof(h));
	scanf("%lld%lld%lld",&n,&m,&k);
	int u,v,w;
	while(m--){
	 	scanf("%lld%lld%lld",&u,&v,&w);
	 	add(u,v,w);
	}
	priority_queue<Nd> q;
	memset(dist,0x3f,sizeof(dist));
	q.push({1,0,dist[1][0]=0});
	while(!q.empty()){
		Nd t=q.top();q.pop();
		int ver=t.u,tim=t.nw_t;
		if(st[ver][t.i]) continue;
		st[ver][t.i]=1;	 
		for(int i=h[ver];~i;i=ne[i]){
			int j=e[i],dis=dist[ver][t.i];
			if(TT[i]>dis) dis+=(TT[i]-dis+k-1)/k*k;
			if(dist[j][(t.i+1)%k]>dis+1){
				dist[j][(t.i+1)%k]=dis+1;
				q.push({j,(t.i+1)%k,dis+1});
			}
		}
	}
	printf("%lld",dist[n][0]==4?-1:dist[n][0]);
	return 0;
}
2023/11/3 07:46
加载中...