题解 | #【模板】单源最短路1#

【模板】单源最短路1

https://www.nowcoder.com/practice/f24504c9ff544f7c808f76693cc34af8

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

typedef long long LL;

const int N = 5050;

struct edge{int v,w;};
vector <edge> e[N];

priority_queue <pair<LL,LL>> q;

bool vis[N];
LL d[N];
int n,m;


void dijkstra(int s){
  memset(d,-1,sizeof d);
  d[s]=0;
  q.push({0,s});
  while(q.size()){
    auto t = q.top();
    q.pop();

    int u =t.second;
    if(vis[u]) continue;
    vis[u]= true;

    for(auto ed:e[u]){
      LL v=ed.v,w=ed.w;
      if(d[v]>d[u]+w||d[v]==-1){
        d[v] =d[u]+w;
        q.push({-d[v],v});
      }
    }

  }

}

int main(){
    cin>>n>>m;
    while(m--){
        int a,b;
        if(a>n||b>n) continue;
        cin>>a>>b;
        e[a].push_back({b,1});
        e[b].push_back({a,1});
    }

    dijkstra(n);
//无向图
    cout<<d[1]<<endl;

    return 0;
}

全部评论

相关推荐

10-30 22:18
已编辑
毛坦厂中学 C++
点赞 评论 收藏
分享
一个菜鸡罢了:哥们,感觉你的简历还是有点问题的,我提几点建议,看看能不能提供一点帮助 1. ”新余学院“别加粗,课程不清楚是否有必要写,感觉版面不如拿来写一下做过的事情,教育经历是你的弱势就尽量少写 2. “干部及社团经历”和“自我评价”删掉 3. 论文后面的“录用”和“小修”啥的都删掉,默认全录用,问了再说,反正小修毕业前肯定能发出来 4. 工作经验和研究成果没有体现你的个人贡献,着重包装一下个人贡献
点赞 评论 收藏
分享
研一开学九月份速成的Java,项目是苍穹外卖和黑马点评,算法基础不好,八股文较为熟练,想找份小厂日常实习,希望牛友们给点意见,蟹蟹啦
求offer的花生米很聪敏:三个月学了这么多?spring springmvc mybatis springboot jvm juc,还做完了两个项目,还熟悉八股,会点算法。卧槽,我该反思了。我暑假开始的,就做了外卖,spring springmvc boot 那些原理好多都忘了,还在刷 jvm 视频,八股和算法也没开始
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务