写了两遍，没过求调

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

XHZnewlife @ 2024-11-17 11:45:05

前后试了两个思路都没过（第一个在弱化版过了）为了写第二个甚至还去专门学了vector…… code1:

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
struct ST{
    int chu;
    int ans;
    map<int,int> mp,lb;
};
ST a[100005];
int dcl[100000];
int hz=1;
void dij(int sta,int lu){
    for(int i=0;i<a[sta].chu;i++){
        if(a[a[sta].lb[i]].ans==INT_MAX){
            dcl[hz]=a[sta].lb[i];
            hz++;
        }
        a[a[sta].lb[i]].ans=min(a[a[sta].lb[i]].ans,lu+a[sta].mp[a[sta].lb[i]]);
    }
    int cl,_min=INT_MAX;
    if(hz==1)return;
    for(int i=1;i<hz;i++){
        if(_min>a[dcl[i]].ans){
            cl=i;
            _min=a[dcl[i]].ans;
        }
    }
    swap(dcl[cl],dcl[hz-1]);
    hz--;
    dij(dcl[hz],_min);
    return;
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)a[i].ans=INT_MAX;
    for(int i=1,u,v,w;i<=m;i++){
        scanf("%d %d %d",&u,&v,&w);
        if(a[u].mp[v]!=0 and v!=s and u!=v)a[u].mp[v]=min(a[u].mp[v],w);
        else if(u!=v and v!=s){
            a[u].lb[a[u].chu]=v;
            a[u].mp[v]=w,a[u].chu++;
        }
    }
    a[s].ans=0;
    dij(s,0);
    a[s].ans=0;
    for(int i=1;i<=n;i++)printf("%d ",a[i].ans);
    return 0;
}

code2:

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
struct ST{
    map<int,int> mp;
    vector<int> lb;
};
ST a[100005];
vector<int> dcl;
int chu[100005],ans[100005];
void dij(int sta,int lu){
    if(sta!=s)dcl.erase(dcl.begin());
    for(int i=0;i<chu[sta];i++){
        ans[a[sta].lb[i]]=min(ans[a[sta].lb[i]],lu+a[sta].mp[a[sta].lb[i]]);
        if(dcl.size()==0)dcl.push_back(a[sta].lb[i]);
        else for(int i=0;i<dcl.size();i++){
            if(ans[dcl[i]]>ans[a[sta].lb[i]]){
                dcl.insert(dcl.begin()+i,a[sta].lb[i]);
                break;
            }
        }
    }
    if(dcl.size()==0)return;
    dij(dcl[0],ans[dcl[0]]);
    return;
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)ans[i]=INT_MAX;
    for(int i=1,u,v,w;i<=m;i++){
        scanf("%d %d %d",&u,&v,&w);
        if(a[u].mp[v]!=0 and v!=s and u!=v)a[u].mp[v]=min(a[u].mp[v],w);
        else if(u!=v and v!=s){
            a[u].lb.push_back(v);
            a[u].mp[v]=w,chu[u]++;
        }
    }
    ans[s]=0;
    dij(s,0);
    ans[s]=0;
    for(int i=1;i<=n;i++)printf("%d ",ans[i]);
    return 0;
}

谢谢诸位dalao

by XHZnewlife @ 2024-11-21 13:34:35

@complete_binary_tree 我又参考了一下其他题解打出来一个，但是if里的条件好像错了，求条

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
struct edge{
    int node,quan;
};
struct dian{
    int num,ans;
    bool operator<(const dian& other)const{
        return ans>other.ans;
    }
};
int ans[100005],flag[100005]={};
vector <edge> ed[100005];
priority_queue<dian> dcl;
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)ans[i]=INT_MAX;
    for(int i=0,u,v,w;i<m;i++){
        cin>>u>>v>>w;
        ed[u].push_back({v,w});
    }
    flag[s]=1;
    ans[s]=0;
    dcl.push({s,0});
    dian cl;
    while(!dcl.empty()){
        cl.ans=dcl.top().ans,cl.num=dcl.top().num;
        dcl.pop();
        for(int i=0;i<ed[cl.num].size();i++){
            cout<<1<<" ";
            if(ans[ed[cl.num][i].node]>cl.ans+ed[cl.num][i].quan and flag[cl.num]!=1){
                ans[ed[cl.num][i].node]=cl.ans+ed[cl.num][i].quan;
                flag[cl.num]=1;
                dcl.push({ed[cl.num][i].node,ans[ed[cl.num][i].node]});
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }
    return 0;
}

谢谢dalao

by complete_binary_tree @ 2024-11-21 15:07:56

你说得对，但是

edge 建议变成 struct edge{int v,w;}，v 和 w 一般表示一条边连向的点和它的边权

vector 可以快速遍历：

vector<int>a;
for(int x:a){cout<<x<<' ';}//输出每一个元素
for(auto x:a){cout<<x<<' ';}//支持自动类型推导
for(auto&x:a){x+=2;}//需要修改时需要加上引用符号&

if(条件1 and 条件2) 可以（最好）改为 if(条件1 && 条件2)。相似的，or \to ||，not \to !。
直接赋值是可行的，如：直接写成 cl=dcl.top()。
尽量不要赋值为 INT_MAX，容易加起来溢出，建议赋值为 1e9，或者直接 memset(数组名,0x3f,sizeof 数组名);

by complete_binary_tree @ 2024-11-21 15:11:19

然后，一个点可以松弛很多个点，所以 flag 是错误的，需要删掉。

还有，为了保证复杂度，需要开 vis 数组来保证每个点只访问一次（被访问后打标记，后面再遇到就别再枚举出边了）。

by complete_binary_tree @ 2024-11-21 16:29:45

@XHZnewlife

by XHZnewlife @ 2024-11-21 19:16:40

@complete_binary_tree 谢谢大佬，终于过了

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
struct edge{
    int node,quan;
};
struct dian{
    int num,ans;
    bool operator<(const dian& other)const{
        return ans>other.ans;
    }
};
int ans[100005],flag[100005]={};
vector <edge> ed[100005];
priority_queue<dian> dcl;
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)ans[i]=INT_MAX;
    for(int i=0,u,v,w;i<m;i++){
        scanf("%d %d %d",&u,&v,&w);
        ed[u].push_back({v,w});
    }
    ans[s]=0;
    dcl.push({s,0});
    dian cl;
    while(!dcl.empty()){
        cl=dcl.top();
        dcl.pop();
        if(flag[cl.num]==1)continue;
        flag[cl.num]=1;
        for(int i=0;i<ed[cl.num].size();i++){
            if(ans[ed[cl.num][i].node]>cl.ans+ed[cl.num][i].quan and flag[ed[cl.num][i].node]!=1){
                ans[ed[cl.num][i].node]=cl.ans+ed[cl.num][i].quan;
                dcl.push({ed[cl.num][i].node,ans[ed[cl.num][i].node]});
            }
        }
    }
    for(int i=1;i<=n;i++){
        printf("%d ",ans[i]);
    }
    return 0;
}

上一页 |