玄学问题求助,悬关
  • 板块灌水区
  • 楼主ChenZQ
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/2/25 09:42
  • 上次更新2024/2/25 13:38:25
查看原帖
玄学问题求助,悬关
745358
ChenZQ楼主2024/2/25 09:42

一下这两个代码我真看不出有什么区别,但是就是一个能过一个61分,求大家帮帮忙

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m;
const int N = 400010;
int h[N],e[N],ne[N],w[N],idx;
void add(int a,int b,int c)
{
	e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
int s,t;
int dist[N][2],cnt[N][2];
bool vis[N][2];
struct node
{
	int u,step,ju;
	bool operator < (const node&cmp) const
	{
		return step>cmp.step;
	}
};
priority_queue<node> q;
int ll=0;

void dijkstra()
{//0 duan 1 ciduan
	q.push({s,0,0});
	for(int i=1;i<=n;i++) dist[i][0]=dist[i][1]=(int)1e18;
	dist[s][0]=0;
	cnt[s][0]=1;
	while(!q.empty())
	{
		node f=q.top();
		q.pop();
		if(vis[f.u][f.ju]) continue;
		vis[f.u][f.ju]=1;
		for(int i=h[f.u];i!=-1;i=ne[i])
		{
			int y=e[i],qq=dist[f.u][f.ju]+w[i];
			if(qq<dist[y][0])
			{
				if(dist[f.u][0]!=(int)1e18)
				{
                    dist[f.u][1]=dist[f.u][0];
                    cnt[f.u][1]=cnt[f.u][0];
                    q.push({y,dist[f.u][1],1});
                }
				dist[y][0]=qq;
				cnt[y][0]=cnt[f.u][f.ju];
				q.push({y,qq,0});
			}
			else if(qq==dist[y][0]) cnt[y][0]+=cnt[f.u][f.ju];
			else if(qq==dist[y][1]) cnt[y][1]+=cnt[f.u][f.ju];
			else if(qq<dist[y][1])
			{
				dist[y][1]=qq;
				cnt[y][1]=cnt[f.u][f.ju];
				q.push({y,qq,1});
			}
		}
	}
	int kkk=0;
	if(dist[t][1]-dist[t][0]==1) kkk=cnt[t][1];
	printf("%lld",cnt[t][0]+kkk);
}
signed main()
{
	memset(h,-1,sizeof h);
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		scanf("%lld%lld%lld",&a,&b,&c);
		add(a,b,c);
	}
	scanf("%lld%lld",&s,&t);
	dijkstra();
}
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
using namespace std;
const int maxd=1005,maxb=20005;
int head[maxd],tot=1;
struct asd{
    int from,to,next,val;
}b[maxb];
void ad(int aa,int bb,int cc){
    b[tot].from=aa;
    b[tot].to=bb;
    b[tot].val=cc;
    b[tot].next=head[aa];
    head[aa]=tot++;
}
struct jie{
    int num,dis,jud;
    jie(int aa=0,int bb=0,int cc=0){
        num=aa,dis=bb,jud=cc;
    }
    bool operator < (const jie& A) const{
        return dis>A.dis;
    }
};
priority_queue<jie> q;
int dis[maxd][3],cnt[maxd][3];
bool vis[maxd][3];
void dij(int xx){
    memset(dis,0x3f,sizeof(dis));
    memset(cnt,0,sizeof(cnt));
    memset(vis,0,sizeof(vis));
    dis[xx][0]=0,cnt[xx][0]=1;
    q.push(jie(xx,0,0));
    while(!q.empty()){
        int now=q.top().num;
        int judd=q.top().jud;
        q.pop();
        if(vis[now][judd]) continue;
        vis[now][judd]=1;
        for(int i=head[now];i!=-1;i=b[i].next){
            int u=b[i].to;
            int ndis=dis[now][judd]+b[i].val;
            if(ndis<dis[u][0]){
                if(dis[u][0]!=0x3f3f3f3f){
                    dis[u][1]=dis[u][0];
                    cnt[u][1]=cnt[u][0];
                    q.push(jie(u,dis[u][0],1));
                }
                dis[u][0]=ndis;
                cnt[u][0]=cnt[now][judd];
                q.push(jie(u,ndis,0));
            }
            else if(ndis==dis[u][0]){
                cnt[u][0]+=cnt[now][judd];
            }
            else if(ndis==dis[u][1]){
                cnt[u][1]+=cnt[now][judd];
            }
            else if(ndis<dis[u][1]){
                dis[u][1]=ndis;
                cnt[u][1]=cnt[now][judd];
                q.push(jie(u,ndis,1));
            }
        }
    }
}
int main(){
    int t;
	t=1;
    while(t--){
        memset(head,-1,sizeof(head));
        memset(&b,0,sizeof(struct asd));
        tot=1;
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=m;i++){
            int aa,bb,cc;
            scanf("%d%d%d",&aa,&bb,&cc);
            ad(aa,bb,cc);
        }
        int qd,zd;
        scanf("%d%d",&qd,&zd);
        dij(qd);
        int ans=cnt[zd][0];
        if(dis[zd][0]==dis[zd][1]-1) ans+=cnt[zd][1];
        printf("%d\n",ans);
    }
    return 0;
}
2024/2/25 09:42
加载中...