求助
查看原帖
求助
315398
小杨小小杨楼主2022/6/8 10:20

假了,求调…………

别发无意义的内容好吗???

#include<bits/stdc++.h>
using namespace std;
long long n,m,l,s,t,x,y,z,dis[4001],vis[4001],hea[4001],head,tot,i,j,tst,tott;
struct Edge{
    long long z,to,nex; 
}edge[4010];
struct Node{
    long long x,y,z;
}a[4010],p[4010];
void ins(long long x,long long y,long long z){
    edge[tot].z=z;
    edge[tot].to=y;
    edge[tot].nex=hea[x];
    hea[x]=tot++;
}
int main(){
    memset(hea,-1,sizeof(hea));
    scanf("%lld%lld%lld%lld%lld",&n,&m,&l,&s,&t);
    for (i=1;i<=m;i++){
        scanf("%lld%lld%lld",&x,&y,&z);
        if (z==0) a[++tott].x=x,a[tott].y=y;
        else ins(x,y,z),ins(y,x,z);
        p[i].x=x;p[i].y=y;p[i].z=z;
    }
    memset(dis,0x3f3f3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    priority_queue< pair<long long,long long> >ps;
    ps.push(make_pair(0,s));
    dis[s]=0;
    while (!ps.empty()){
       	long long head=ps.top().second;
        ps.pop();
        if (!vis[head]){
           	vis[head]=1;
        	for (i=hea[head];~i;i=edge[i].nex){
            	long long v=edge[i].to;
            	if (dis[head]+edge[i].z<dis[v]){
            		dis[v]=dis[head]+edge[i].z;
            		ps.push(make_pair(-dis[v],v));
            	}
           	}
        }
    }
    if (dis[t]<l){
        printf("NO\n");
        return 0;
    }
    else if (dis[t]==l){
        printf("YES\n");
        for (i=1;i<=m;i++)
            if (p[i].z==0) printf("%lld %lld 1000000000000000000\n",p[i].x,p[i].y);
            else printf("%lld %lld %lld\n",p[i].x,p[i].y,p[i].z);
        return 0;
    }
    else{
        for (tst=1;tst<=tott;tst++){
            ins(a[tst].x,a[tst].y,1);
            ins(a[tst].y,a[tst].x,1);a[tst].z=1;
            memset(dis,0x3f3f3f,sizeof(dis));
            memset(vis,0,sizeof(vis));
            priority_queue< pair<long long,long long> >q;
            dis[s]=0;
            q.push(make_pair(0,s));
            while (!q.empty()){
            	long long head=q.top().second;
            	q.pop();
            	if (!vis[head]){
           			vis[head]=1;
            		for (i=hea[head];~i;i=edge[i].nex){
            			long long v=edge[i].to;
            			if (dis[head]+edge[i].z<dis[v]){
            				dis[v]=dis[head]+edge[i].z;
            				q.push(make_pair(-dis[v],v));
            			}
            		}
            	}
            }
            if (dis[t]==l){
                printf("YES\n");
                long long sum=1;
                for (i=1;i<=m;i++)
                    if (p[i].z==0){
                        if (sum<=tst) printf("%lld %lld %lld\n",a[sum].x,a[sum].y,a[sum].z),sum++;
                        else printf("%lld %lld 1000000000000000000\n",p[i].x,p[i].y);
                    }
                    else printf("%lld %lld %lld\n",p[i].x,p[i].y,p[i].z);
                return 0;
            }
            else if (dis[t]<l){
                printf("YES\n");
                a[tst].z=l-dis[t]+1;
                long long sum=1;
                for (i=1;i<=m;i++)
                    if (p[i].z==0){
                        if (sum<=tst) printf("%lld %lld %lld\n",a[sum].x,a[sum].y,a[sum].z),sum++;
                        else printf("%lld %lld 1000000000000000000\n",p[i].x,p[i].y);
                    }
                    else printf("%lld %lld %lld\n",p[i].x,p[i].y,p[i].z);
                return 0;
            }
        }
    }
    printf("NO\n");
    return 0;
}
2022/6/8 10:20
加载中...