题目这里进==》P4822[BJWC2012] 冻结

不会分层图模版,没看出来哪错了,向神犇们求助

蟹蟹大佬们!!!

#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
const int N=205;
int n,m;
int k;
bool vis[N];
int d[N];
int ans=inf;
int cnt=0;
int head[N*50];
struct Edge{
	int next;
	int to;
	int time;
}edge[N*50];
void add(int u,int v,int w){
	edge[cnt].next=head[u];
	edge[cnt].to=v;
	edge[cnt].time=w;
	head[u]=cnt++;
}
void dijkstra(){
	priority_queue<pair<int,int> > q;
	q.push(make_pair(0,1));
	d[1]=0;
	while(q.size()){
		int x=q.top().second;
		q.pop();
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i!=-1;i=edge[i].next){
			int y=edge[i].to;
			if(d[y]>d[x]+edge[i].time){
				d[y]=d[x]+edge[i].time;
				q.push(make_pair(-d[y],y));
			}
		}
	}
}
int main(){
	memset(vis,false,sizeof(vis));
	memset(d,0x3f,sizeof(d));
	memset(head,-1,sizeof(head));
	cin>>n>>m>>k;
	for(int i=1;i<=m;i++){
		int a,b,time;
		cin>>a>>b>>time;
		for(int j=0;j<=k;j++){
			add(j*n+a,j*n+b,time);
			add(j*n+b,j*n+a,time);
		}
        for(int j=0;j<k;j++){
			add(j*n+a,(j+1)*n+b,time/2);
			add(j*n+b,(j+1)*n+a,time/2);
        }
	}
	dijkstra();
	for(int i=0;i<=k;i++)
		if(ans<d[i*n+n]) ans=d[i*n+n];
	cout<<ans;
	return 0;
}