单源最短路问题
可以求出指定某个点到其他所有点的最短距离
邻接矩阵的构造
没有相连接的两个结点的距离时无穷大，本身到本身为0，其他正常
1.先把所有的结点的距离初始化为无穷大
2.本身与本身的距离设为0
3.输入距离
距离数组的构造
构造一个一维距离数组来记录该点到其他点的最短距离
1.进行赋值，从邻接矩阵中赋值
2.本身到本身设为0
O(n^2)
对每一个点进行遍历
找个该点的相连点中，距离该点最近的点，然后标记最近点
从标记的最近点进行遍历最近点相连接的点，进行距离更新
因为距离用的是指定某个点的距离，所以最后求出来的距离数组是对于该点来说的
相当于求出某个点a到另个点b的最短距离，然后这个距离和指定点到b的距离进行比大小，求距离短的那条路
比如
遍历为1时，表示结点为1的点进行查找，找到1的最近点，
然后对该点的连接点进行查找，比较指定点到这个点的距离和指定点先到1再到这个点的距离哪个近，近的变成指定点到该点的距离
Problem Description
某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
Input
本题目包含多组数据，请处理到文件结束。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。
Output
对于每组数据，请在一行里输出最短需要行走的距离。如果不存在从S到T的路线，就输出-1.
Sample Input
3 3
1 2 1
1 3 3
2 3 1
1 3
3 1
1 2 1
2 3
Sample Output
2
-1
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define INF 1000000
#define bug printf("aaa");
using namespace std;
const int maxn=1005;
int edges[maxn][maxn];//邻接矩阵表示
int n;//点的数
int m;//边数
int dis[maxn];//储存指定点到其他点的距离
int vis[maxn];//标记顶点是否被访问过
void init(){
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
if(i==j)edges[i][j]=0;//到本身的距离
else edges[i][j]=INF;//无穷大
}
vis[i]=0;
}
int a,b,d;
for(int i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&d);
if(edges[a][b]>d){
edges[a][b]=edges[b][a]=d;
}
}
}
void Dij(int s){
for(int i=1;i<=n;i++){
dis[i]=edges[s][i];
}
vis[s]=1;//初始点标记
int minn,mark;//进行查找，找到与当前点相连接的且距离最短的一个点，进行标记
for(int i=1;i<=n;i++){
minn=INF;
for(int j=1;j<=n;j++){
if(vis[j]==0&&dis[j]<minn){
minn=dis[j];
mark=j;
}
}
vis[mark]=1;//标记该点
//对这个标记点的相连点进行距离更新
for(int k=1;k<=n;k++){//遍历所有点
if(edges[mark][k]<INF){//如果说当前的点与前面标记的点相互连接
if(vis[k]==0&&dis[k]>dis[mark]+edges[mark][k]){//进行判断，看看是否可以更新为更小的的距离
//dis[k]是指定点到该点的距离，dis[mark]是指定点标记点的距离，edges[mark][k]是标记点到该点的距离
dis[k]=dis[mark]+edges[mark][k];
}
}
}
}
}
int main(){
while(scanf("%d%d",&n,&m)==2&&n&&m){
init();//初始化并且创建；邻接矩阵
int s,t;
scanf("%d%d",&s,&t);
Dij(s);
if(dis[t]==INF){
printf("-1\n");
}else{
printf("%d\n",dis[t]);
}
}
return 0;
}最短路问题2，在距离的基础上加个价格，距离相同时，得到价格最小的
promblem description
给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
Input
输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)
Output
输出 一行有两个数， 最短距离及其花费。
Sample Input
3 2
1 2 5 6
2 3 4 5
1 3
0 0
Sample Output
9 11
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define INF 1000000
#define bug printf("aaa");
using namespace std;
const int maxn=1005;
int edges[maxn][maxn];//邻接矩阵表示
int edgec[maxn][maxn];
int n;//点的数
int m;//边数
int dis[maxn];//储存指定点到其他点的距离
int vis[maxn];//标记顶点是否被访问过
int cost[maxn];
void init(){
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
if(i==j){
edges[i][j]=0;//到本身的距离
edgec[i][j]=0;
}
else{
edges[i][j]=INF;//无穷大
edgec[i][j]=INF;
}
}
vis[i]=0;
}
int a,b,d,p;
for(int i=0;i<m;i++){
scanf("%d%d%d%d",&a,&b,&d,&p);
if(edges[a][b]>d){
edges[a][b]=edges[b][a]=d;
edgec[a][b]=edgec[b][a]=p;
}
}
}
void Dij(int s){
for(int i=1;i<=n;i++){
dis[i]=edges[s][i];
cost[i]=edgec[s][i];
}
int minn,mark;
for(int i=1;i<=n;i++){
minn=INF;
for(int j=1;j<=n;j++){
if(vis[j]==0&&dis[j]<minn){
minn=dis[j];
mark=j;
}
}
vis[mark]=1;
for(int k=1;k<=n;k++){
if(edges[mark][k]<INF){
if(vis[k]==0&&dis[k]>dis[mark]+edges[mark][k]){
dis[k]=dis[mark]+edges[mark][k];
cost[k]=cost[mark]+edgec[mark][k];
}else if(vis[k]==0&&dis[k]==dis[mark]+edges[mark][k]){
if(cost[k]>cost[mark]+edgec[mark][k]){
cost[k]=cost[mark]+edgec[mark][k];
}
}
}
}
}
}
int main(){
while(scanf("%d%d",&n,&m)==2&&n&&m){
init();//初始化并且创建；邻接矩阵
int s,t;
scanf("%d%d",&s,&t);
Dij(s);
printf("%d %d\n",dis[t],cost[t]);
}
return 0;
}输入描述:
第一行四个数n，m,s,t。(分别表示有地图上n个地点，m条道路，SSJ在s处，他家在t处)第2-m+1三个正整数，f，u(某条路起点)，v(到达点)，w(路径距离)。(f为1或0,0表示这条道路上有恶狗拦路，SSJ已无力与恶狗打斗了，所以他要避开这些道路，1表示此条道路无危险)。
输出描述:
第一行一个数表示最短路径长度，若无法回家输出“My gold!!!”(无引号)若可以回家.
示例1
输入
5 7 1 5
0 1 4 4
1 1 3 2
1 1 5 7
1 2 5 10
0 2 3 1
1 3 5 2
1 4 3 7
输出
4
备注:
n≤10000,m≤200000,w≤5000000
//dijkstra优先队列
#include<bits/stdc++.h>
using namespace std;
const int inf=1000000002;
const int maxn=100100,maxm=200200;
int head[maxm],vis[maxn],dis[maxn];
int i,j;
int u,v,w,z;
int n,m,s,t;
int cnt=1;
struct edge
{
int to;
int nx;
int w;
}e[maxm];
inline void add(int u,int v,int w)
{
e[cnt].to=v;
e[cnt].w=w;
e[cnt].nx=head[u];
head[u]=cnt;
cnt++;
}
struct node
{
int dis;
int pos;
bool operator < (const node &x)const
{
return x.dis<dis;
}
} ;
std::priority_queue<node> q;
inline void dijkstra()
{
q.push((node){0,s});
while(!q.empty())
{
node tmp=q.top();
q.pop();
int x=tmp.pos,d=tmp.dis;
if(vis[x])
continue;
vis[x]=1;
for(i=head[x];i;i=e[i].nx)
{
int y=e[i].to;
if(dis[y]>dis[x]+e[i].w)
{
dis[y]=dis[x]+e[i].w;
q.push((node){dis[y],y});
}
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
for(i=1;i<=n;i++)
dis[i]=inf;
dis[s]=0;
for(i=1;i<=m;i++)
{
scanf("%d%d%d%d",&z,&u,&v,&w);
if(z==1)
{
add(u,v,w);
add(v,u,w);
}
}
dijkstra();
if(dis[t]!=inf)
printf("%d",dis[t]);
else printf("My gold");
}原文：https://www.cnblogs.com/Emcikem/p/11333851.html