C++语言（单源最短路）_#include bool a[10000002]; vector s

只有一丢~的代码（附加一些不知道对不对的口胡）

至于图吗，，，，，我想后期我会补上~只是我想~~~~

先贴上

#include<iostream>
#include<cstdio>
#include<string.h>
#define Tnf 2147483647 
/*
fist[一个点x]=边 表示x这个点连接的第一条边是谁
next[一条边mm]=边kk 表示mm这条边连接的下一条边的名字叫kk
to[一条边xx]=一个点y1 表示xx这条边连向的点是y1
weight[一条边]=一个值， 是表示这个边的权值 
*/
using namespace std;
int n,m,s;
long long int dis[500001],next[500001],head[500001],book[500001],to[500001],w[500001],tot=0;
void add(int a,int b,int c)
{
    /*要知道，邻接表中(加边操作)只能是通过第一条边是谁来查找，要想插入每一条边，只能是通过不断的更新第一条便来实现的，先让现在插入的边连接目前该电
    的第一条边，然后把应该插入的点视为该点的第一条边*/
    tot++;
    to[tot]=b;
    w[tot]=c; 
    next[tot]=head[a];
    head[a]=tot;
}
/*
dijkstra 的一般步骤，1.从一个点开始搜索，不断计算长度（先初始化，如果两路不通，直接输出最大值即可，speciallist dis这个数组也是会因为开始的源点不同而变化，每次都更新还是有必要的） 
                     2.每一次都是从不同的点进行的dijkstra,所以每一次的标记与否的点都是不一样的，应该每次都清空book标记数组(这个地方要注意啊string.h)
                     3.（这些都是小事，应该会记住）首先计算dijkstra的时候，应该吧这个标记的点到自己的距离设为0，                 
                     4.按顺序依次找每一个点的最小dis，（for循环依次找就OK了）
                     5.注意在找的过程中，首先要明确的是★开始要找的点一定是没有找过的点啊，★这个点的dis一定是连接出发点中最小的点（不然的话，那这个点去松弛，这个点既然不是最小的点
                     去松弛也没啥意思，问题是，松弛完了，结果是错的....还要注意的是，找的最小的点以后加入集合，即打上标记，） ★找到了这个符合要求的点进行松弛操作就可以了 
*/
void dijkstra(int u)
{
 
//  memset(dis,Tnf,sizeof(dis));
    for(int i=1;i<=n;i++)dis[i]=Tnf;
    memset(book,0,sizeof(book));
    dis[u]=0;
    for(int i=1;i<=n;i++)
    {
        int start=-1;
        for(int j=1;j<=n;j++)
        {
            if(book[j]==0&&(dis[j]<dis[start]||start==-1))start=j;
        }   
        book[start]=1;
        for(int e=head[start];e;e=next[e])
        {
            dis[to[e]]=min(dis[to[e]],dis[start]+w[e]);
        }
    }   
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=0;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++)cout<<dis[i]<<" "; 
} 
/*
make a summary
其一 错误很明显了 ，每次都是忘记找该点连接的最小的一条边，然后就乱松弛，结果全wa
其二 在松弛时 e=haed[start];e;e=next[e] 以及dis[to[e]]=min(dis[top[e]],dis[start]+w[e])     (也就是核心代码记得一点都不熟) 
 
*/ 

本人比较喜欢邻接表 ~~邻接矩阵也似很好啊 map[a][b]=c；

以下是堆优化以后的（用来对付升级版的~~~）

#include<queue>
#include<cstdio>
#include<stdio.h>
#include<iostream>
#include<string.h>
using namespace std;
int tot=0,next[100100002],w[1000002],to[1000002],first[10000002], vis[10000002], dis[10000002];
struct node
{
    int d,id;
    bool operator <(const node &a)const
    {
    return d>a.d;
    }
};
void add(int a,int b,int c)
{
    tot++;
    next[tot]=first[a];
    to[tot]=b;
    w[tot]=c;
    first[a]=tot;
}
priority_queue<node> q;
void dijkstra(int s)
{
    memset(dis,0x7f,sizeof(dis));
    dis[s]=0;
    q.push((node){0,s});
    while(!q.empty())
    {                                                                                    
        int x=q.top().id;
        q.pop();
        if(vis[x])continue;  
        vis[x]=1;
        for(int i=first[x];i;i=next[i])
        {
            int y=to[i];
            if(vis[y])continue;
            if(dis[y]>dis[x]+w[i])
            {
                dis[y]=dis[x]+w[i];
                q.push((node){dis[y],y});
            }
        }
    }
}
int main()
{
    int n,m,s;
    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++)cout<<dis[i]<<" ";
}