我AC了，但是我觉得我是可以Hacked的，但是我又不会hack

我用的是邻接表和朴素版Dijkstra。在我找到目前距离包含s点的那个集合最短的点之后，我应该用它更新该点到别的点的距离。于是我利用零接表，遍历了这个点可以到的所有边。理论上来说边有5E5个，这一步操作O(m)。但是我没有去重边，如果边有这样的： 1->2 0x3f 1->2 0x3f 1->2 0x3f 1->2 0x3f ... 有很多，那么我得一步步遍历这些重复的边。如果考虑去重的话...零接表也可以去重边吗？见多识广的大佬干脆给我普及一下吧！假如没有，那么破局之道在哪里呢？

这是我的存储方式：

CPP

const int MAXV=1E4+10;
const int MAXE=5E5+10;

struct Edge{
    int ne;
    int v;
    int w;
}e[MAXE];

int head[MAXV];
bool Graph_vis[MAXV];
int Graph_cnt;
int dis[MAXV];

void init(){
    for(int i=0;i<MAXV;i++){ head[i]=-1; e[i].ne=-1; Graph_vis[i]=0;}
    return;
}

void add(int u,int v,int w){
    e[Graph_cnt].w=w;
    e[Graph_cnt].v=v;
    e[Graph_cnt].ne=head[u];
    head[u]=Graph_cnt++;
    return;
}

这是我的Dijkstra代码：

CPP

void solve(){
    
    init();
    int n,m,s;
    cin>>n>>m>>s;
    
    for (int i=1; i<=m; i++) {
        int x,y,w;
        cin>>x>>y>>w;
        add(x,y,w);
    }
    
    for (int i=1; i<=n; i++) {
        dis[i]=Inf;
    }
    dis[s]=0;
    
    for (int j=1; j<=n; j++) {
        int _max=Inf;
        int close=-1;
        for (int i=1; i<=n; i++) {
            if(dis[i]<_max&&!Graph_vis[i]){
                _max=dis[i];
                close=i;
            }
        }
        if(close==-1) break;
        Graph_vis[close]=1;
        for (int i=head[close]; ~i; i=e[i].ne) {
            dis[e[i].v]=min(dis[e[i].v],dis[close]+e[i].w);
        }
    }
    for (int i=1; i<=n; i++) {
        cout<<dis[i]<<" ";
    } cout<<endl;
    
    return;
}

我AC了，但是我觉得我是可以Hacked的，但是我又不会hack

讨论操作

回复

相关推荐

我AC了，但是我觉得我是可以Hacked的，但是我又不会hack