样例没过交上去ac
查看原帖
样例没过交上去ac
794083
Z3k7223ios::sync楼主2024/7/17 14:50

如题,我的代码在本地和ide测试两个样例都输出0,但是提交ac,没查出错

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=5e5+10,inf=2e9;
int k,n,n_,m,s,t;
struct node{
	int v,w;
	friend bool operator<(node x,node y){
		return x.w>y.w;
	}
};
vector<node>e[N];
int dis[N];
void add(int u,int v,int w){
	e[u].push_back({v,w});
}
void dij() {
	priority_queue<pii>q;
	q.push(make_pair(s,0));
	for(int i=1;i<n_;i++){
		dis[i]=inf;
	}
	dis[s]=0;
	while(!q.empty()){
		pii tmp=q.top();
		q.pop();
		int x=tmp.first;
		if(tmp.second>dis[x]){
			continue;
		}
		int lim=e[x].size();
		for(int i=0;i<lim;i++){
			int v=e[x][i].v;
			int w=e[x][i].w;
			if(dis[v]>dis[x]+w){
				dis[v]=dis[x]+w;
				q.push({v,dis[v]});
			}
		}
	}
}
int main(){
	cin>>k>>n>>m;
	n_=k*n;
	for(int i=1;i<=m;i++){
		int u,v,w,w2;
		cin>>u>>v>>w>>w2;
		for(int j=0;j+w2<k;j++){
			add(j*n+u,(j+w2)*n+v,w);
			add(j*n+v,(j+w2)*n+u,w);
		}
	}
	cin>>s>>t;
	dij();
	int ans=inf;
	for(int i=0;i<k;i++){
		if(dis[i*n+t]!=inf){
			ans=min(ans,dis[i*n+t]);
		}
	}
	cout<<(ans==inf?-1:ans)<<endl;
	return 0;
}
2024/7/17 14:50
加载中...