正文之前
好久没弄C++了，上学期颓废了半学期，这学期开学就搞课程设计快疯了。待会要考试CSP，所以弄点代码储备，待会到了考场说不定能省点功夫！
正文
#include<iostream>
using namespace std;
#define The_Bigest_Num 1000000
#define BIGEST 10000
int Tu[BIGEST][BIGEST];
bool Judge_IF_IS_IN_MIN[BIGEST];
int Distance[BIGEST];
int Qian_Qu[BIGEST];
void dijkstra(int v0,int n)
{
//初始化参数，设定所有与初始点相连的点的前驱点为初始点
for(int i=1;i<=n;++i)
{
Judge_IF_IS_IN_MIN[i]=false;
Distance[i]=Tu[v0][i];
if(Distance[i]!=The_Bigest_Num)
Qian_Qu[i]=v0;
else
Qian_Qu[i]=-1;
}
//设置初始点到初始点的距离为0，其他为Tu[v0][i];
Distance[v0]=0;
Judge_IF_IS_IN_MIN[v0]=true;
//对除了初始点外的每个点进行最短路径的计算。
for(int i=2;i<=n;++i)
{
int min_distance=The_Bigest_Num;
int u=v0;
for(int j=1;j<=n;++j)
{
//扫描每个点，如果不是处于最短路径状态并且距离小于当前最小距离，那么更新当前最小距离，并且找到出发点到某一点的最小距离。
if(!Judge_IF_IS_IN_MIN[j] && Distance[j]<min_distance)
{
u=j;
min_distance=Distance[j];
}
}
//找到了初始点点到某一点的最小距离之后，从别的点开始找到当前点有么有更近的点。
Judge_IF_IS_IN_MIN[u]=true;
// int minQianQu=The_Bigest_Num;
for(int j=1;j<=n;++j)
{
if(!Judge_IF_IS_IN_MIN[j] && Tu[u][j]<The_Bigest_Num) //Tu[u][j]<minQianQu)
{
if(Distance[j]>=Distance[u]+Tu[u][j])
{
Distance[j]=Distance[u]+Tu[u][j];
Qian_Qu[j]=u;
// minQianQu=Tu[u][j];
}
}
}
}
int all=0;
for(int i=2;i<=n;++i)
{
if(Qian_Qu[i]!=1)
{
all+=(Distance[i]-Distance[Qian_Qu[i]]);
}
else
all+=Tu[1][i];
}
cout<<all<<endl;
}
int main()
{
int lines,size;
cin>>size>>lines;
for(auto &x:Tu)
for(auto &s:x)
s=The_Bigest_Num;
while(lines--)
{
int a,b,c;
cin>>a>>b>>c;
Tu[a][b]=c;
Tu[b][a]=c;
}
dijkstra(1,size);
}
/*
样例输入
4 5
1 2 4
1 3 5
2 3 2
2 4 3
3 4 2
样例输出
11
*/
Output：
Last login: Sun Mar 18 12:09:36 on ttys000
= * = * = * = * = * = * = * = * = * = * = * = * = * = *
✧｡٩(ˊᗜˋ)و✧* Hello！ Welcome 张照博！！开启愉快的一天吧！
= * = * = * = * = * = * = * = * = * = * = * = * = * = *
HustWolf:~ zhangzhaobo$ /Users/zhangzhaobo/program/C++/Dijkstra ; exit;
4 5
1 2 4
1 3 5
2 3 2
2 4 3
3 4 2
11
logout
Saving session...
...copying shared history...
...saving history...truncating history files...
...completed.
[进程已完成]
正文之后
祝我好运！发誓这次考试后一定苦学！上学期太飘了。
