求助

P4779 【模板】单源最短路径(标准版)

gyc071116 @ 2024-07-25 08:22:12

疑问:第28行for循环中“j<tu[now_node].size()”改为“j<=tu[now_node].size()-1”为什么会RE

#include<bits/stdc++.h>
using namespace std;
struct edge{
    int value;
    int in;
};
vector<edge> tu[100005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
int path[100005];
void edge_add(int node_out,int node_in,int val){
    edge a;
    a.in=node_in;
    a.value=val;
    tu[node_out].push_back(a);
}
int main(){
    int n,m,s;
    memset(path,63,sizeof(path));
    scanf("%d %d %d",&n,&m,&s);
    path[s]=0;
    int u,v,w;
    for(int i=1;i<=m;i++){
        scanf("%d %d %d",&u,&v,&w);
        edge_add(u,v,w);
    }
    int now_node=s;
    for(int i=1;i<=n;i++){
        for(int j=0;j<tu[now_node].size();j++){
            if(path[tu[now_node][j].in]>path[now_node]+tu[now_node][j].value){
                path[tu[now_node][j].in]=path[now_node]+tu[now_node][j].value;
                q.push(make_pair(path[tu[now_node][j].in],tu[now_node][j].in));
            }
        }
        int path_min;
        while(!q.empty()){
            if(q.top().first==path[q.top().second]){
                path_min=q.top().first;
                now_node=q.top().second;
                q.pop();
                break;
            }
            else q.pop();
        }
    }
    for(int i=1;i<=n;i++) printf("%d ",path[i]);
    return 0;
}

(以上代码可AC)


by GCSG01 @ 2024-07-25 08:28:59

应该是 .size 为无符号整数,当 size 为0时,0-1 就会溢出。


by gyc071116 @ 2024-07-25 08:55:28

@GCSG01 懂了,谢谢大佬


|