注:这是原笔记,本人蒟蒻一名,没加优化
#include<stdio.h>
#include<algorithm>
#define inf 0xfffffff
using namespace std;
//graph[x][y]指点x到y的权值
int n,m,graph[105][105]={};
int sw[106]={};//点1到点n的最小权值
bool mk[106]={};//标记数组,mk[n]=true表示当前点1到点n是最短的
int main()
{
int v1,v2,w;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) //初始化权,Dijkstra求最短路必须初始化
{
for(int j=1;j<=n;j++)
graph[i][j]=inf;
sw[i]=inf;
graph[i][i]=0;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&v1,&v2,&w);
//邻接矩阵的最短路径一定要注意两点多边问题
graph[v1][v2]=graph[v2][v1]=min(graph[v1][v2],w);//v1到v2的权为原来的权值和w中最小的
}
int finish;
printf("input finish:");
scanf("%d",&finish);//输入终点
sw[1]=0;
for(int k=1;k<=n;k++)
{
int mn=inf,pos=1;
for(int i=1;i<=n;++i)
if(mk[i]==0&&mn>sw[i])
mn=sw[i],pos=i;
mk[pos]=1;//标记pos点
for(int i=1;i<=n;++i)//以POS点向周围扩散
if(mk[i]==0&&sw[i]>sw[pos]+graph[i][pos])
sw[i]=sw[pos]+graph[i][pos];
}
printf("point %d to %d:%d",1,finish,sw[finish]);
return 0;
}