stl档舒服了 ^_^

类似的做法，使用了unordered_map

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;
const int N = 100005;
int m, n;
int dis[N], st[N];
unordered_map<int, vector<PII>> mp;

int dijkstra(){
    memset(dis, 0x3f, sizeof dis);
    dis[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({dis[1], 1});
    while(!pq.empty()){
        auto t = pq.top();
        pq.pop();
        int index = t.second;
        if (st[index]) continue;
        st[index] = 1;
        for (auto it: mp[index]){
            int k = it.first;
            int len = it.second;
            if (dis[k] > dis[index] + len){
                dis[k] = dis[index] + len;
                pq.push({dis[k], k});
            }
        }
    }
    if (dis[n] == 0x3f3f3f3f) return -1;
    return dis[n];

}

int main(){
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        mp[a].push_back({b, c});
    }
    int k = dijkstra();
    cout << k << endl;
    return 0;
}

map 也挺好的 哈哈

很适合我这种看不懂数组模拟链表的。。爱了

int newnode = gra[node][i].first;
int len = gra[node][i].second;
你前面不是说first是距离,second是节点吗?怎么又反了

vector重边怎么处理

重边的计算 不影响得到最短的距离

可以可以，stl舒服

想请问一下，gra.resize(n+1)的参数为什么是n+1而不是n呀

习惯问题，因为C语言索引从0开始，如果要访问n下标， 其实是有0~n ,需要有n+1个空间。

谢谢

您好 这题用邻接矩阵会不会内存开辟过大 用vector[HTML_REMOVED]> 是不是会稍微好一点，可以帮忙分析一下吗 感谢

如果都是使用vector，数量上差不太多，看个人喜好，读代码更通顺为准。没啥区别。
如果严格要求减少空间和时间的消耗，Y总的链式星的存储办法才是最优的。

感谢

tql

适合面试党，我觉得要跟面试官解释h, idx什么的都费大劲了

是的，哈哈。 不过比较好的图论代码，可以看看力扣的图论中，速度中等偏上的代码，一般可读性都蛮强的。

大佬牛逼，我也是用的这种方法，一直报Segmentation Fault ，看了你的才知道是少了这一句 gra.resize(n + 1);
这是因为下标从1开始，所以要手动分配空间吗

嗯 ,1到n 可不就是从0开始的n+1个空间吗

不过我后面还是老老实实的去学习了链式前向星

那为啥还要加行 gra.resize(n + 1);呢

因为是二维数组，这里是初始化第一维，第二维还是空的

想问下楼主 gra的first不用清成inf吗

vector和数组稍有区别，push_back才 有元素，不pushback没有元素。
所以只要gra有元素都是确认的数据，

for (int i = 0; i < m; i++) {
        int a, b, c;
        //cin >> a >> b >> c;
        scanf("%d %d %d",&a,&b,&c);
        //这里是 目的节点号在前 边长在后
        gra[a].push_back({ b,c });
    }

不存在清空或者初始化

first不是存到的那条边吗？？

代码写了注释
//这里是 目的节点号在前 边长在后

楼主可以问一个问题吗， priority_queue[HTML_REMOVED], greater[HTML_REMOVED]> heap 怎么是两个数据，不应该是四个吗 priority_queue<[HTML_REMOVED], vector[HTML_REMOVED], greater[HTML_REMOVED]> heap

格式看的不太清楚，我大概尝试回答下。这个看具体的用法，优先队列有时候可以省略一些参数，里面自行创建了vector存储数据。

楼主能问一下，如果heap的first存编号的话，那该如何写重载< 的来达到first存距离的效果呢

priority_queue[HTML_REMOVED], greater[HTML_REMOVED]> heap; 声明里面 修改这个greater[HTML_REMOVED]，就是他的排序依据。 可以添加自定义的比较函数的

真的爱了~~我还以为只有我用双vector来模拟邻接表

然而后面的题目就TLE了，还是老实的去学习链向星了。hh

大佬可以问一个问题吗，就是主函数里的gra.resize(n + 1)是做什么的 谢谢!!

c++里的数组动态设定长度，
因为设置全局变量的时候 还不知道图中点和线段有多大。
这个在写竞赛题目的时候 不怎么用，而是预先设置最大长度即可。
我习惯写leetcode 所以写法可能不太常用。

评论里 hongrubb   的代码 才是常用写法

typedef pair<int, int> PII;
const int N = 100005;
int m, n;
int dis[N], st[N];
unordered_map<int, vector<PII>> mp;

可以这样写

const int N = 100010;
vector<PII> gra[N];
int dist[N];
int st[N];

能不能解释一下，大佬们。

就是Y总得模板 把Y总得数组改成了更习惯用的vector

我是刚来的，请问是Y总的课吗，还是模板？？？