MAXtoDEATH 2022-07-06 22:06 采纳率: 50%
浏览 13

CAIP 2021 段错误

请问C题中这种RE的情况您有遇到过吗
谢谢

img


```c++
#include"stdio.h"
#include"string.h"
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=4000;
const int inf=1e9+10;
struct cmp_struct {
    int u;
    int dis1;
    int dis2;
};

struct cmp {
    bool operator()(cmp_struct a,cmp_struct b) {
        if(a.dis1!=b.dis1) {
            return a.dis1<b.dis1;
        } else {
            return a.dis2>b.dis2;
        };
    }
};
int nextx[maxn];
int head[maxn];
int len1[maxn];
int len2[maxn];
int to[maxn];
int cnt=0;
int E[maxn][maxn];
int dis1[maxn];
int dis2[maxn];
bool vis[maxn];
int pre_node[maxn];
//priority_queue<cmp_struct,vector<cmp_struct>,cmp> pq;
queue<int>q;
void add(int u,int v,int w1,int w2) {
    cnt++;
    to[cnt]=v;
    len1[cnt]=w1;
    len2[cnt]=w2;
    nextx[cnt]=head[u];
    head[u]=cnt;
}
void print_pre(int x){
    if(pre_node[x]!=-1){
        print_pre(pre_node[x]);
        printf("->%d",x);
    }
    else{
        printf("%d",x);
    }
}
void dij(int st) {
    dis1[st]=0;
    dis2[st]=0;
    cmp_struct cx={st,0,0};
    //pq.push(cx);
    q.push(st);
    while(!q.empty()){
        /*cmp_struct item=pq.top();
        pq.pop();
        int u=item.u;*/
        int u=q.front();
        q.pop();
        if(vis[u]) continue;
        vis[u]=true;
        for(int i=head[u];i>0;i=nextx[i]){
            int d1=len1[i];
            int d2=len2[i];
            int uto=to[i];
            /*if(uto==u){
                printf("ERROR!!!\n");
            }*/
            if(d1+dis1[u]<dis1[uto]){
                dis1[uto]=d1+dis1[u];
                dis2[uto]=d2+dis2[u];
                pre_node[uto]=u;
                //pq.push({uto,dis1[uto],dis2[uto]});
                q.push(uto);
            }
            else if(d1+dis1[u]==dis1[uto]&&d2+dis2[u]>dis2[uto]){
                dis2[uto]=d2+dis2[u];
                pre_node[uto]=u;
                //pq.push({uto,dis1[uto],dis2[uto]});
                q.push(uto);
            }
        }
    }
}
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        dis1[i] = inf;
        pre_node[i] = -1;
    }
    memset(E,0x3f,sizeof(E));
    for(int i=0; i<m; i++) {
        int u,v,w1,w2;
        scanf("%d%d%d%d",&u,&v,&w1,&w2);
        E[u][v]=w1;
        E[v][u]=w1;
        add(u,v,w1,w2);
        add(v,u,w1,w2);
    }
    for(int k=1; k<=n; k++) {
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(E[i][k]+E[k][j]<E[i][j])
                    E[i][j]=E[i][k]+E[k][j];
            }
        }
    }
    int nmaxn=0,st;
    int tmaxn=inf,tst;
    for(int i=1;i<=n;i++){
        nmaxn=0;
        for(int j=1;j<=n;j++){
            nmaxn=max(E[i][j],nmaxn);
            st=i;
        }
        if(nmaxn<tmaxn){
            tmaxn=nmaxn;
            tst=st;
        }
    }
    printf("%d\n",tst);
    
    dij(tst);
    int q;
    scanf("%d",&q);
    for(int i=0;i<q;i++){
        int tmp;
        scanf("%d",&tmp);
        print_pre(tmp);
        printf("\n%d %d\n",dis1[tmp],dis2[tmp]);
    }
    return 0;
}


  • 写回答

1条回答 默认 最新

  • 赵4老师 2022-07-07 11:45
    关注

    输入输出格式
    边界条件
    ……

    评论

报告相同问题?

问题事件

  • 创建了问题 7月6日

悬赏问题

  • ¥15 素材场景中光线烘焙后灯光失效
  • ¥15 请教一下各位,为什么我这个没有实现模拟点击
  • ¥15 执行 virtuoso 命令后,界面没有,cadence 启动不起来
  • ¥50 comfyui下连接animatediff节点生成视频质量非常差的原因
  • ¥20 有关区间dp的问题求解
  • ¥15 多电路系统共用电源的串扰问题
  • ¥15 slam rangenet++配置
  • ¥15 有没有研究水声通信方面的帮我改俩matlab代码
  • ¥15 ubuntu子系统密码忘记
  • ¥15 保护模式-系统加载-段寄存器