写了两遍，没过求调

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-17 11:49:58

第一段试了尽量少用结构体，然而也只是16-->32,所以感觉不是结构体在耗时间

by complete_binary_tree @ 2024-11-17 11:54:05

为什么要把dijkstra写成递归形式呢？增加114514倍常数还不好写。
本题普通SPFA过不了，去学个优先队列优化的罢。

by FFFuuuFFFuuu @ 2024-11-17 11:56:32

？？dalao你学了dijkstra才学vector吗？

by XHZnewlife @ 2024-11-19 21:35:11

@complete_binary_tree 大体还是原来的，排序方式改了一下，不T了，但是全WA了，求条

#include<bits/stdc++.h>
using namespace std;
int n,m,s;

struct ST{
    int chu,lan,num;
    int ans;
    map<int,int> mp,lb;
    bool operator<(const ST& other) const{
        return ans<other.ans;
    }
};
ST a[100005];
priority_queue<ST> dcl;
int hz=1;
void dij(int sta,int lu){
    if(sta!=s)dcl.pop();
    for(int i=0;i<a[sta].chu;i++){
        a[a[sta].lb[i]].ans=min(a[a[sta].lb[i]].ans,lu+a[sta].mp[a[sta].lb[i]]);
        if(a[a[sta].lb[i]].lan==0){
            dcl.push(a[a[sta].lb[i]]);
            a[a[sta].lb[i]].lan=1;
        }
    }
    if(dcl.size()==0)return;
    dij(dcl.top().num,dcl.top().ans);
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++){
        a[i].ans=INT_MAX;
        a[i].num=i;
    }
    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,a[s].lan=1;
    dij(s,0);
    a[s].ans=0;
    for(int i=1;i<=n;i++)printf("%d ",a[i].ans);
    return 0;
}

谢谢dalao

by complete_binary_tree @ 2024-11-20 12:16:03

dij为什么不写成dfs形式呢？

truct ST{
  int u,dis
  friend bool operator<(ST a,ST b){return a.dis<b.dis;}
};//u当前节点dis距离 重载小于号
priority_queue<ST>pq;
inline void dij(){
  memset(dis,0x3f,sizeof dis);
  dis[start]=0;//开始点设为0
  pq.push(start);
  while(!pq.empty()){
    auto u=pq.top().u;pq.pop();
    for(枚举出边v){
      //边权为w
      if(dis[u]+w<dis[v])q.push({u,dis[u]+w});
    }
  }
}

by complete_binary_tree @ 2024-11-20 12:16:32

呸，说错了，是为什么不写成bfs形式

by complete_binary_tree @ 2024-11-20 12:20:48

存边建议使用vector（别用map）

vector<pair<int,int>>e[100005];

加边（u\to v 边权 w）

e[u].push_back(make_pair(v,w));

遍历出边


//第一种方式（C++17及以上）
for(auto [v,w]:e[u]){
  //v去向 w边权
}
//第二种方式
for(auto i:e[u]){
  int v=i.first,w=i.second;
  //v去向 w边权
}

by complete_binary_tree @ 2024-11-20 12:22:01

而且pq里存map是效率很低的行为，存边要和dijs的结构体分开

by complete_binary_tree @ 2024-11-20 12:22:12

@XHZnewlife

by XHZnewlife @ 2024-11-20 19:21:11

@complete_binary_tree 好的，谢谢大佬，我好好看看，我现在只有晚上能到机房

| 下一页