马蜂良好60pts玄关球条
查看原帖
马蜂良好60pts玄关球条
750476
Hf_Poem楼主2024/9/5 15:07

WA on #1 #7 #9 #10(好抽象

#include<bits/stdc++.h>
#define setp(a) fixed<<setprecision(a)
#define Venti cout<<"\nVenti!\n";
#define int long long
#define il inline
using namespace std;
const int V=1e4+10,M=5*V;
int n,m,dis[V],st[V],wa[M],way1[M],way2[M];
int h[V],e[M],ne[M],val1[M],val2[M],idx=1;
il void add(int a,int b,int v1,int v2){
	e[idx]=b,ne[idx]=h[a],val1[idx]=v1,val2[idx]=v2,h[a]=idx++;
}
void dij(int op,int *w){
	memset(st,0,sizeof st);
    memset(dis,0x3f,sizeof dis);
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > qu;
    dis[n]=0,qu.push({0,n});
    while(!qu.empty()){
        auto t=qu.top();
        qu.pop();
        int u=t.second,dist=t.first;
        if(st[u]==0){
        	st[u]=1;
	        for(int i=h[u];i!=-1;i=ne[i]){
	            int v=e[i];
	            if(dis[v]>dist+w[i]){
	            	way1[v]=u,way2[v]=i;
	                dis[v]=dist+w[i];
	                qu.push({dis[v],v});
	            }
	        }
		}
    }
    int zc=1;
	while(zc!=n){
		wa[way2[zc]]--;
		zc=way1[zc];
	}
	if(op==1) cout<<dis[1];
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	memset(h,-1,sizeof h);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		wa[i]=2;
	for(int i=1;i<=m;i++){
		int x,y,v1,v2;
		cin>>y>>x>>v1>>v2;
		add(x,y,v1,v2);
	}
	dij(0,val1),dij(0,val2),dij(1,wa);
	return 0;
}
/*
4 5
1 2 1 114
1 3 114 1
3 2 1 1
2 4 1 1
3 4 1 3
*/

球球各位大佬辣!!!!!

2024/9/5 15:07
加载中...