一个MLE，一个WA，求改

P4779 【模板】单源最短路径（标准版）

stylus @ 2024-01-24 09:00:29

第一个（这个其实能过，但MLE了：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,h;
};
bool operator <(node a,node b){
    return a.h>b.h;
}
int n,m,s,a[10001][10001],d[10001],u,v,w;
void bfs(){
    priority_queue<node>q;
    q.push({s,0}),d[s]=0;
    while(q.size()){
        node s=q.top();
        q.pop();
        for(int i=1;i<=n;i++){
            if(a[s.x][i]==-1)continue;
            if(d[i]>d[s.x]+a[s.x][i])d[i]=d[s.x]+a[s.x][i],q.push({i,d[i]});
        }
    }for(int i=1;i<=n;i++)cout<<d[i]<<' ';
    return;
}
int main(){
    memset(a,-1,sizeof(a)),memset(d,114514,sizeof(d));
    cin>>n>>m>>s;
    for(int i=0;i<m;i++)cin>>u>>v>>w,a[u][v]=w;
    bfs();
    return 0;
}

然后我又改了一下（却错了：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,h;
};
bool operator <(node a,node b){
    return a.h>b.h;
}
int n,m,s,d[10001],u,v,w;
map<pair<int,int>,int>mp;
void bfs(){
    priority_queue<node>q;
    q.push({s,0}),d[s]=0;
    while(q.size()){
        node s=q.top();
        q.pop();
        for(int i=1;i<=n;i++){
            if(mp[{s.x,i}]==-1)continue;
            if(d[i]>d[s.x]+mp[{s.x,i}])d[i]=d[s.x]+mp[{s.x,i}],q.push({i,d[i]});
        }
    }for(int i=1;i<=n;i++)cout<<d[i]<<' ';
    return;
}
void init(){
    memset(d,114514,sizeof(d));
    mp.clear();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j)mp[{i,j}]=-1;
        }
    }return;
}
int main(){
    init();
    cin>>n>>m>>s;
    for(int i=0;i<m;i++)cin>>u>>v>>w,mp[{u,v}]=w;
    bfs();
    return 0;
}

求大佬改正！！！

by __My0217__ @ 2024-01-24 09:12:51

d[]初始成inf

by stylus @ 2024-01-24 09:24:03

@My0217 第一个代码改了之后还是MLE：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,h;
};
bool operator <(node a,node b){
    return a.h>b.h;
}
int n,m,s,a[10001][10001],d[10001],u,v,w;
void bfs(){
    priority_queue<node>q;
    q.push({s,0}),d[s]=0;
    while(q.size()){
        node s=q.top();
        q.pop();
        for(int i=1;i<=n;i++){
            if(a[s.x][i]==-1)continue;
            if(d[i]>d[s.x]+a[s.x][i])d[i]=d[s.x]+a[s.x][i],q.push({i,d[i]});
        }
    }for(int i=1;i<=n;i++)cout<<d[i]<<' ';
    return;
}
int main(){
    memset(a,-1,sizeof(a)),memset(d,0x3f3f3f3f,sizeof(d));
    cin>>n>>m>>s;
    for(int i=0;i<m;i++)cin>>u>>v>>w,a[u][v]=w;
    bfs();
    return 0;
}

第二个改了之后还是WA：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,h;
};
bool operator <(node a,node b){
    return a.h>b.h;
}
int n,m,s,d[10001],u,v,w;
map<pair<int,int>,int>mp;
void bfs(){
    priority_queue<node>q;
    q.push({s,0}),d[s]=0;
    while(q.size()){
        node s=q.top();
        q.pop();
        for(int i=1;i<=n;i++){
            if(mp[{s.x,i}]==-1)continue;
            if(d[i]>d[s.x]+mp[{s.x,i}])d[i]=d[s.x]+mp[{s.x,i}],q.push({i,d[i]});
        }
    }for(int i=1;i<=n;i++)cout<<d[i]<<' ';
    return;
}
void init(){
    memset(d,0x3f3f3f3f,sizeof(d));
    mp.clear();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(i!=j)mp[{i,j}]=-1;
        }
    }return;
}
int main(){
    init();
    cin>>n>>m>>s;
    for(int i=0;i<m;i++)cin>>u>>v>>w,mp[{u,v}]=w;
    bfs();
    return 0;
}

怎么办？

by __My0217__ @ 2024-01-24 09:34:47

@5520qq 百度一下dijkstra算法，改进你的bfs

by stylus @ 2024-01-24 09:48:35

@My0217 主要是第二个代码和第一个代码相比，只是把int改成了map,为什么就做不出来了?

注：第一个其实能过，但MLE了

by __My0217__ @ 2024-01-24 09:55:54

@5520qq

  1. 第二个代码为啥 i!=j时才赋成-1
  2. 学习邻接表，1e5*1e5的邻接矩阵会爆

by __My0217__ @ 2024-01-24 09:56:45

第一条说的是第二个代码的init部分。

by stylus @ 2024-01-24 10:22:02

@My0217 

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,h;
};
bool operator <(node a,node b){
    return a.h>b.h;
}
int n,m,s,d[10001],u,v,w;
map<pair<int,int>,int>mp;
void bfs(){
    priority_queue<node>q;
    q.push({s,0}),d[s]=0;
    while(q.size()){
        node s=q.top();
        q.pop();
        for(int i=1;i<=n;i++){
            if(d[i]>d[s.x]+mp[{s.x,i}])d[i]=d[s.x]+mp[{s.x,i}],q.push({i,d[i]});
        }
    }for(int i=1;i<=n;i++)cout<<d[i]<<' ';
    return;
}
void init(){
    memset(d,0x3f3f3f3f,sizeof(d));
    mp.clear();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)mp[{i,j}]=-1;
    }return;
}
int main(){
    init();
    cin>>n>>m>>s;
    for(int i=0;i<m;i++)cin>>u>>v>>w,mp[{u,v}]=w;
    bfs();
    return 0;
}

可还是错的呀

by __My0217__ @ 2024-01-24 10:26:23

@5520qq 为啥你bfs()里面if(mp[{s.x,i}]==-1)continue;没了

by stylus @ 2024-01-24 10:32:51

@My0217 改成连接表（不太会，也错了：

#include<bits/stdc++.h>
using namespace std;
struct node{
    int x,h;
};
bool operator <(node a,node b){
    return a.h>b.h;
}
int n,m,s,d[10001],u,v,w;
vector<pair<int,int>>a[10001];
void bfs(){
    priority_queue<node>q;
    q.push({s,0}),d[s]=0;
    while(q.size()){
        node s=q.top();
        q.pop();
        for(int i=0;i<a[s.x].size();i++){
            if(d[i]>d[s.x]+a[s.x][i].second)d[i]=d[s.x]+a[s.x][i].second,q.push({a[s.x][i].first,d[i]});
        }
    }for(int i=1;i<=n;i++)cout<<d[i]<<' ';
    return;
}
int main(){
    memset(a,-1,sizeof(a)),memset(d,0x3f3f3f3f,sizeof(d));
    cin>>n>>m>>s;
    for(int i=0;i<m;i++)cin>>u>>v>>w,a[u].push_back({v,w});
    bfs();
    return 0;
}

by stylus @ 2024-01-24 10:34:51

@My0217 因为if(mp[{s.x,i}]==-1)continue;加了跟没加了一样

| 下一页