题目选自洛谷P3371

这个数据类型可以将两个数据进行打包，比如

pair<int,int>

就是将两个int型进行打包。

而且使用优先队列时，优先队列会根据你打包的第一个数据进行排序。

那么问题来了，怎么将他们打包呢？

有个函数叫做make_pair()。

使用时：

make_pair(0,1);

即把 0,1 打包。

好了，现在我们可以直接使用

priority_queue<int,vector<pair<int,int> >,greater<pair<int,int> > >q;

就可以省去写排序函数了。

其中pair的第一个数存长度，第二个数存节点编号。

 

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入格式

第一行包含三个整数 n,m,s，分别表示点的个数、有向边的个数、出发点的编号。

接下来 m 行每行包含三个整数 u,v,w，表示一条 u→v 的，长度为 w 的边。

输出格式

输出一行 n 个整数，第 i 个表示 s 到第 i 个点的最短路径，若不能到达则输出 2^31−1。

输入输出样例

输入 1

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出 1

0 2 4 3

说明/提示

【数据范围】
对于 20% 的数据：1≤n≤5，1≤m≤15；
对于 40% 的数据：1≤n≤100，1≤m≤10^4；
对于 70% 的数据：1≤n≤1000，1≤m≤10^5；
对于 100% 的数据：1≤n≤104，1≤m≤5×10^5，1≤u,v≤n，w≥0，∑w<2^31，保证数据随机。

对于真正 100% 的数据，请移步 P4779。请注意，该题与本题数据范围略有不同。

样例说明：

图片1到3和1到4的文字位置调换

解题代码：

#include<bits/stdc++.h>
using namespace std;

int n,m,s;

struct node
{
    int next,to,len;
}edge[500005];

int cnt;
int head[100005];
bool visit[100005];
int dis[100005];

priority_queue<int,vector<pair<int,int> >,greater<pair<int,int> > >q;

void Add(int a,int b,int c)
{
    cnt++;
    edge[cnt]=(node){head[a],b,c};
    head[a]=cnt;
}

int main()
{
    for(int i=0;i<100005;i++) head[i]=0;
    for(int i=0;i<100005;i++) dis[i]=INT_MAX;
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        Add(a,b,c);
    }
    dis[s]=0;
    q.push(make_pair(0,s));      //将源点入队
    while(!q.empty())
    {
    	int now=q.top().second;     //取节点编号
    	q.pop();    //弹出
    	if(visit[now]) continue;    //已经遍历过
        visit[now]=true;
        for(int i=head[now];i;i=edge[i].next) if(!visit[edge[i].to] && dis[edge[i].to]>dis[now]+edge[i].len)     //标准前向星遍历
        {
            dis[edge[i].to]=dis[now]+edge[i].len;
            q.push(make_pair(dis[edge[i].to],edge[i].to));    //入队
        }
    }
    for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
    return 0;
}