https://www.luogu.org/problem/show?pid=2299#sub
题目背景
ｍｚｃ与ｄｊｎ第四弹。
题目描述
ｍｚｃ家很有钱（开玩笑），他家有ｎ个男家丁（做过前三弹的都知道）。但如此之多的男家丁吸引来了我们的体委（矮胖小伙），他要来与ｍｚｃ争夺男家丁。
ｍｚｃ很生气，决定与其决斗，但ｃａｔ的体力确实有些不稳定，所以他需要你来帮他计算一下最短需要的时间。
输入输出格式
输入格式：
第一行有两个数ｎ，ｍ，ｎ表示有ｎ个停留站，ｍ表示共有ｍ条路。
之后ｍ行，每行三个数ａ［ｉ］，ｂ［ｉ］，ｃ［ｉ］，表示第ａ［ｉ］个停留站到第ｂ［ｉ］个停留站需要ｃ［ｉ］的时间。（无向）
输出格式：
一行，输出１到ｍ最短时间。
输入输出样例
输入样例#1：
5 8 1 2 3 2 3 4 3 4 5 4 5 6 1 3 4 2 4 7 2 5 8 1 5 100
输出样例#1：
11
说明
ｎ＜＝２５００
由于mzc大大十分着急，所以他只能等待1S。
建图时判重
1 #include <algorithm> 2 #include <iostream> 3 #include <cstdio> 4 #define maxn 3015 5 #define inf 1000000007 6 7 using namespace std; 8 9 int n,x,m,minn,y,z,ans; 10 int dis[maxn][maxn]; 11 int d[maxn]; 12 bool vis[maxn]; 13 14 void Dijkstra(int n) 15 { 16 for(int i=1;i<=n;i++) 17 d[i]=dis[1][i]; 18 d[1]=0,vis[1]=true; 19 int k; 20 for(int i=1;i<n;i++) 21 { 22 minn=inf; 23 for(int j=1;j<=n;j++) 24 if(d[j]<minn&&!vis[j]) 25 { 26 minn=d[j]; 27 k=j; 28 } 29 30 vis[k]=1; 31 if(k==n) break; 32 for(int j=1;j<=n;j++) 33 if(!vis[j]&&d[j]>d[k]+dis[k][j]) 34 d[j]=d[k]+dis[k][j]; 35 } 36 37 } 38 39 int main() 40 { 41 scanf("%d%d",&n,&m); 42 for(int i=1;i<=n;i++) 43 for(int j=1;j<=n;j++) 44 dis[i][j]=inf; 45 for(int i=1;i<=m;i++) 46 { 47 cin>>x>>y>>z; 48 dis[x][y]=dis[y][x]=min(z,dis[x][y]); 49 } 50 Dijkstra(n); 51 cout<<d[n]; 52 return 0; 53 }