简单分层图求条,玄关
查看原帖
简单分层图求条,玄关
654577
RainySoul楼主2024/10/12 09:39
#include<bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f
using namespace std;
const int N=200010;
struct node{
	int dis,loc,cnt,las;
	friend bool operator <(node x,node y){
		return x.dis>y.dis||(x.dis==y.dis&&x.cnt>y.cnt);
	}
};
struct zyx{
	int to,w;
};
struct csq{
	int to,w,tim,xh,num;
};
vector<zyx> e[N];
vector<csq> a[N];
priority_queue<node> q;
int n,m,dis[N][110],s,k,t;
bool vis[N][110]; 
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
void dijkstra(){
	memset(dis,inf,sizeof dis);
	q.push((node){t,1,-1,0});
	dis[1][-1]=t;
	while(!q.empty()){
		int u=q.top().loc,cnt=q.top().cnt,las=q.top().las;
//		cout<<"现在走到了"<<u<<" "<<q.top().cnt<<" "<<q.top().dis<<" "<<las<<'\n'; 
		q.pop();
//		if(vis[u][cnt])continue;
//		vis[u][cnt]=1;
		for(int i=0;i<a[u].size();i++){
			int to=a[u][i].to,w=a[u][i].w;
			//还要算这班车啥时候到我这里  即 dis[u]距离车来还有多久 
			int lun=ceil((dis[u][cnt]-a[u][i].tim)*1.0/a[u][i].xh);
			int temp=a[u][i].tim+lun*a[u][i].xh,tt;
			if(dis[u][cnt]<=a[u][i].tim)temp=a[u][i].tim;	
//			cout<<to<<"="<<a[u][i].num<<",las="<<las<<'\n'; 
			if(las==a[u][i].num){
				if(dis[to][cnt]>w+temp){
					dis[to][cnt]=w+temp;
					q.push((node){dis[to][cnt],to,cnt,a[u][i].num});
				}
			}
			else if(cnt+1<=k){
				if(dis[to][cnt+1]>w+temp){
					dis[to][cnt+1]=w+temp;
					q.push((node){dis[to][cnt+1],to,cnt+1,a[u][i].num});
				}
			}
//			if(dis[u]<a[u][i].tim)temp=a[u][i].tim-dis[u];
//			cout<<"到达"<<to<<"的temp为"<<temp<<'\n';
			
		}
	}
}
signed main(){
	n=read(),m=read();
	s=read(),k=read(),t=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),w=read();
		e[u].push_back((zyx){v,w});
		e[v].push_back((zyx){u,w});
	} 
	for(int i=1;i<=s;i++){
		int c=read(),x=read(),y=read();
		int now=read(),d=0;
		for(int j=2;j<=c;j++){
			int t=read();
			for(int k=0;k<e[now].size();k++){
				int to=e[now][k].to;
				if(to==t){
					a[now].push_back((csq){to,e[now][k].w,d+x,y,i});
					//在新图中有一条从 now到 to的边权为 w的边,第一次出发时间为 d+x,循环时间为y 
					d+=e[now][k].w;
					now=to;
					break;
				}
			}
		}	
	}
//	cout<<"check连边\n";
//	for(int i=1;i<=n;i++){
//		cout<<i<<":\n";
//		for(int j=0;j<a[i].size();j++){
//			cout<<a[i][j].to<<" "<<a[i][j].w<<" "<<a[i][j].tim<<" "<<a[i][j].xh<<'\n'; 
//		}
//	}
//	cout<<'\n';
	dijkstra(); 
	int ans=inf;
	for(int i=0;i<=k;i++)ans=min(ans,dis[n][i]);
	if(ans==inf)cout<<"NIE";
	else{
		cout<<ans;	
	}
	return 0;
}
/*
这个列车的时间就相当于在某时刻开启了一条
从 a[i][j]到 a[i][j+1]的边
时间循环,两次之间间隔 y
你发现你走到一个点之后如果有列车线路经过你肯定可以等到 
 
*/
2024/10/12 09:39
加载中...