luoguP3371【模板】单源最短路径（Dijkstra+优先队列优化）

题目描述

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

输入输出格式

输入格式：

第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。

输出格式：

一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）

输入输出样例

输入样例#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

说明

时空限制：1000ms,128M

数据规模：

对于20%的数据：N<=5，M<=15

对于40%的数据：N<=100，M<=10000

对于70%的数据：N<=1000，M<=100000

对于100%的数据：N<=10000，M<=500000

样例说明：

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

分析
和FPSA一样Dijkstra+优先队列优化也有两种写法这里就写了两种补充前面缺少的向量（vector）的写法，这里的优先队列是STL和之前的堆优化效果一样，但是有些说写的方法不一样于是还是加以区分，不过本题好像并没有什么影响，在下面用堆代替优先队列（代码实现的效果是一样）
首先是邻接表(由于向量的注释已经很详细了，就不添加邻接表的注释了)

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define N 10005 
#define M 500005
#define INF 2147483647
using namespace std;
int head[M],Next[M],val[M],vet[M],tot;
void add(int x,int y,int z){
    tot++;
    vet[tot]=y;
    val[tot]=z;
    Next[tot]=head[x];
    head[x]=tot;
};
int n,m,d[N],done[N];
struct cmp{
    bool operator()(int x,int y){return d[x]>d[y];}
};
void Dijkstra(int s){
    priority_queue<int,vector<int>,cmp>q;
    for(int i=1;i<=n;i++)d[i]=INF;
    d[s]=0;q.push(s);
    while(!q.empty()){
        int u=q.top();q.pop();
        if(done[u])continue;
        done[u]=1;
        for(int i=head[u];i;i=Next[i]){
            int v=vet[i];
            if(d[v]>d[u]+val[i]){
                d[v]=d[u]+val[i];
                q.push(v);
            }
        }
    }
}    
int s;
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    Dijkstra(s);
    for(int i=1;i<n;i++)
        printf("%d ",d[i]);
    printf("%d",d[n]);
    return 0;
}

然后就是vector

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
#define N 10005
#define M 500005
#define INF 2147483647//题目要求
using namespace std;
struct edge{
    int from,to,dist;
    edge(int u,int v,int d):from(u),to(v),dist(d){}//结构体函数调用方便之后堆里的出入队
};
struct heapnode{
    int d,u;
    bool operator<(const heapnode&rhs)const{
        return d>rhs.d;
    }//结构体的比较函数，使用cmp也可以有这样的效果
};
vector<int>g[N];//g[N]数组其实也可以省略，不过要涉及到另一个STL<pair>其实我觉得不怎么方便还会无辜的加一点东西就不用了QwQ
vector<edge>edges;
int n,m,d[N],done[N];//相当于visit数组
void Dijkstra(int s){
    priority_queue<heapnode>q;//建堆
    for(int i=1;i<=n;i++)d[i]=INF;
    d[s]=0;q.push((heapnode){0,s});//初始化，入队
    while(!q.empty()){
        heapnode x=q.top();q.pop();//取堆顶元素
        int u=x.u;
        if(done[u])continue;//如果已经用过就返回
        done[u]=1;
        for(int i=0;i<g[u].size();i++){//枚举所有的连通点
            edge e=edges[g[u][i]];
            if(d[e.to]>d[u]+e.dist){
                d[e.to]=d[u]+e.dist;
                q.push((heapnode){d[e.to],e.to});
            }//标准的Dijsktra写法
        }
    }
}
int s;
int main(){
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        edges.push_back(edge(a,b,c));
        int mm=edges.size();
        g[a].push_back(mm-1);//vector数组从0开始存储和char类数组一样所以说要-1；表示的是该边的位置
    }
    Dijkstra(s);
    for(int i=1;i<n;i++)
        printf("%d ",d[i]);
    printf("%d",d[n]);
    return 0;
}