题解 | #【模板】单源最短路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个岗位
点赞 评论 收藏
分享
12-01 12:34
已编辑
广东工业大学 Java
如题,fw🐭🐭,加上准备的太晚,大三上已找不到日常实习,导致连锁反应,下学期的暑期实习找不到好的实习,导致秋招找不到中大厂,现在是中小厂Java还有考公的选择,由于有些中小厂工作强度比肩大厂,钱还少,感觉不如考公如果🐮u们是我现在这种情况,会怎么选?
负债的混子:关注你一段时间了,突然发现你头像名字都改了,想必是这段时间压力很大。关于就业还是考公的选择,就像很多牛友说的:不要美化自己没走过的路。你现在想往互联网发展,发现这条路很难走,然后想往考公发展,但是你没走过考公这条路,所以你不知道这条路的压力如何。你今年大三了,还有时间给你做选择,我希望你能够尽快的决定自己的方向,然后一条路走到黑,而不是在这里徘徊,每个人的道路是不一样的,你无法复刻别人的路,你能做的就是尽力的完善自己。 最后,我想说的是,加油,陌生人!
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务