单源最短路径【东北大学oj数据结构12-2/3】C++

题面

对于给定的加权图 G=(V,E)，找到从源到每个结点的最短路径。 对于每个结点 u，打印从结点 0 到 u 的最短路径上边的总权重。

输入

在第一行中，给出了一个整数 n，表示 G 中的结点数。
在接下来的n行中，每个结点u的邻接表分别以如下格式给出：
u k v1​ c1​ v2​ c2​ ... vk​ ck​
其中：
G 中的结点从 0 ~ n-1 编号。
u 是目标结点的 ID，k 表示它的度数。
vi​(i=1,2,...k) 表示与 u 相邻的结点的 ID，ci​ 表示连接 u 和 vi​（从 u 到 vi​）的有向边的权重。

输出

对于每个结点，分别在一行中打印其 ID 和距离（使用空格分隔）。
注意，需按结点 ID 的顺序打印。

约束

1≤n≤100
0≤ci​≤100,000
|E|≤10,000
所有结点都可以从结点 0 到达

输入样例

5
0 3 2 3 3 1 1 2
1 2 0 2 3 4
2 3 0 3 3 1 4 1
3 4 2 1 0 1 1 4 4 3
4 2 2 1 3 3

输出样例

0 0
1 2
2 2
3 1
4 3 

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef pair<int,int> pii;
void dijkstra(int n,const vector<vector<pii>>& adj)
{
    vector<int> dist(n,INT_MAX);
    dist[0]=0;
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    pq.push({0,0});
    while(!pq.empty())
    {
        int u=pq.top().second;
        int d=pq.top().first;
        pq.pop();
        if(d>dist[u]) continue;
        for(int i=0;i<adj[u].size();i++)
        {
            int v=adj[u][i].first;
            int weight=adj[u][i].second;
            if(dist[u]+weight<dist[v])
            {
                dist[v]=dist[u]+weight;
                pq.push({dist[v],v});
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        cout<<i<<" "<<dist[i]<<endl;
    }
}
 
int main() {
    int n;
    cin >> n;
   vector<vector<pii>> adj(n);
    for(int i=0;i<n;i++)
    {
        int u,k;
        cin>>u>>k;
        for(int j=0;j<k;j++)
        {
            int v,c;
            cin>>v>>c;
            adj[u].push_back({v,c});
        }
    }
    dijkstra(n,adj);
    return 0;
}