【最短路】求最短路的几种算法（更新中）

还是markdown好用，会HTML就能搞点?好? 东西
最近发现伪码是个好东西。
<好>啊

单源最短路

Dijkstra算法

（荷兰人名字多少带点怪（滑稽））

算法思想

在我看来，是在只关心路的长度的情况下，找没有用过的最短边去凑。是一种贪心。
具体说：
从一个点出发到图中任何一个点，每两点之间的距离最多只需要检查一次就足够计算出最短路了。
1.设起点到每个点的距离为无穷大
2.找到最小的边，更新起点到这个点的距离
重复2直到检查过所有的边为止。
3.输出到目标点的距离

伪码

初始化vis（设为否）和d数组（d[起点]=0，d[别的]=INF）
（vis判断是否被访问过，d[i]记录起点到i的距离）
循环n次{
  在所有未vis过的边里，选出d最小的点x
  给x标记
  对于从x出发的所有边，更新：
    d[y]=min{d[y],d[x]+w(x->y)
}

优化

看到这，我知道：最麻烦的事情变成如何找到最短的没被访问过的边？
优先队列出马。
接下来还想问：怎么存图？
?随便。
不过我喜欢链式前向星

代码实现

#include
#include
#define maxn 10050000
#define INF 1000000000
using namespace std;

struct edge{
    int next;
    int to;
    int v;
}e[maxn];
struct node{
    int d;
    int x;
    bool operator <(const node &a)const{
        return d q;
int head[maxn],vis[maxn],d[maxn],n,m,s,cnt;

void add(int x,int y,int w){
    e[++cnt].to=y;
    e[cnt].v=w;
    e[cnt].next=head[x];
    head[x]=cnt;
}

void Dijkstra(){
    for(int i=1;id[x]+e[i].v)
                d[y]=d[x]+e[i].v;
            if(!vis[y]) 
                q.push((node){d[y],y});
        }
    }
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i>a>>b>>w;
        add(a,b,w);
    }
    Dijkstra();
    for(int i=1;i