題目大意
這道題要我們求一群奶牛最短的回家的路更舞，題目會(huì)給你n個(gè)點(diǎn)，m條邊坎吻，然后給你每條邊又哪兩個(gè)點(diǎn)相連缆蝉，并且其中的路程是多少。我們需要找到最短路徑的總路程瘦真。
樣例輸入
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
樣例輸出
90
分析
坑點(diǎn)1：這邊和點(diǎn)是倒著給的 刊头， 你需要先輸入邊再輸入點(diǎn)。
坑點(diǎn)2：他會(huì)給你重復(fù)的邊吗氏，比如1和2之間的距離是100芽偏，然后又給你說1和2之間的距離是80。當(dāng)然我們可以理解為1和2之間有兩條路弦讽，但是我就因?yàn)檫@個(gè)wa了好多發(fā)污尉。當(dāng)然，我們構(gòu)建鄰接矩陣的時(shí)候需要選擇最短的那條路往产。
剩下的就dijkstra一波帶走被碗。代碼如下。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define CLR(x) memset(x,0,sizeof(x))
using namespace std;
const int INF = 100000;
const int maxp = 1100;
const int maxl = 1000000;
int edge[maxp][maxp];
int dist[maxp];
int vis[maxp];
int p,l;
int dijkstra(int x) //磁少風(fēng)格版
{
for(int i = 1 ; i <= p ; i++)
dist[i] = INF;
int v = x;
dist[v]=0;
vis[v]=1;
for(int i = 1 ; i <= p ; i++)
{
for(int j = 1; j <= p ; j++)
{
if(vis[j]!=1 && dist[v]+edge[v][j] < dist[j])
{
dist[j] = dist[v] + edge[v][j];
}
}
int minn = INF;
for(int j = 1 ; j <= p ; j++)
if(vis[j]!=1 && dist[j] < minn)
{
minn=dist[j];
v=j;
}
vis[v]=1;
}
}
int main()
{
while(scanf("%d%d",&l,&p)!= EOF)
{
for(int i = 0 ; i < maxp ; i++)
{
for(int j = 0 ; j < maxp ; j++)
{
edge[i][j] = INF;
}
edge[i][i] = 0;// 因?yàn)榭赡茌斎胫貜?fù)兩條邊的值我們需要選出同樣的邊最小的那一個(gè)值仿村；
}
CLR(vis);
for(int i = 1 ; i <= l ; i++)
{
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
if(edge[u][v] > w)
{
edge[u][v] = edge[v][u] = w;
}
}
dijkstra(1);
printf("%d\n",dist[p]);
}
}
