求助 WA#6

Creative_sad_yosgic @ 2023-01-08 20:11:54

#include<bits/stdc++.h>
using namespace std;
int dis[311111],vis[311111];
vector<int> mp[311111];
map<int,map<int,int> > w;
int s;
typedef struct edge{
    int num,dis;
    bool operator < (const edge &b) const{
        return dis>b.dis;
    }
};
priority_queue<edge> q;
void dijkstra(int x,int st){
    memset(dis,0x3f,sizeof(dis));
    dis[st]=0;
    edge y;
    y.num=st;
    y.dis=0;
    q.push(y);
    while(!q.empty()){
        edge c=q.top();
        q.pop();
        if(vis[c.num]) continue;
        vis[c.num]=1;
        for(int i=0;i<mp[c.num].size();i++)
        {
            if(dis[mp[c.num][i]]>dis[c.num]+w[c.num][mp[c.num][i]]){
                dis[mp[c.num][i]]=dis[c.num]+w[c.num][mp[c.num][i]];
                if(!vis[mp[c.num][i]])
                q.push((edge){mp[c.num][i],dis[mp[c.num][i]]});
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    //freopen("6.in","r",stdin);
    //freopen("6.out","w",stdout);
    int n,m,s;
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int x,y,w1;
        cin>>x>>y>>w1;
        mp[x].push_back(y);
        if(w[x][y]) w[x][y]=min(w[x][y],w1);
        else w[x][y]=w1;
    }
    dijkstra(n,s);
    for(int i=1;i<=n;i++){
        if(dis[i]!=0x3f3f3f3f) cout<<dis[i]<<" ";
        else cout<<2147483647<<" ";
    }
    return 0;
}

by wanggk @ 2023-01-08 20:21:51

@csy114514

或许正好是存图的问题。以下代码，我把原来代码的存图方式进行修改，把二维的map换掉就可以AC了。

实在不建议这么存图，结构体打包非常方便。

#include<bits/stdc++.h>
using namespace std;
int dis[311111],vis[311111];
//map<int,map<int,int> > w;
int s;
typedef struct edge{
    int num,dis;
    bool operator < (const edge &b) const{
        return dis>b.dis;
    }
};
vector<edge> mp[311111];//改成了edge
priority_queue<edge> q;
void dijkstra(int x,int st){
    memset(dis,0x3f,sizeof(dis));
    dis[st]=0;
    edge y;
    y.num=st;
    y.dis=0;
    q.push(y);
    while(!q.empty()){
        edge c=q.top();
        q.pop();
        if(vis[c.num]) continue;
        vis[c.num]=1;
        for(int i=0;i<mp[c.num].size();i++)
        {
            if(dis[mp[c.num][i].num]>dis[c.num]+mp[c.num][i].dis){
                dis[mp[c.num][i].num]=dis[c.num]+mp[c.num][i].dis;
                if(!vis[mp[c.num][i].num])
                q.push((edge){mp[c.num][i].num,dis[mp[c.num][i].num]});
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    //freopen("6.in","r",stdin);
    //freopen("6.out","w",stdout);
    int n,m,s;
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int x,y,w1;
        cin>>x>>y>>w1;
        mp[x].push_back((edge){y,w1});//加边直接打包结构体扔进去，免去了二维map
//        if(w[x][y]) w[x][y]=min(w[x][y],w1);
//        else w[x][y]=w1;
    }
    dijkstra(n,s);
    for(int i=1;i<=n;i++){
        if(dis[i]!=0x3f3f3f3f) cout<<dis[i]<<" ";
        else cout<<2147483647<<" ";
    }
    return 0;
}

by Creative_sad_yosgic @ 2023-01-08 20:23:29

感谢，学会了新的存图方式