暢通工程續(xù)

Time Limit: 3000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9566????Accepted Submission(s): 3200

Problem Description 某省自從實行了很多年的暢通工程計劃后，終于修建了很多路。不過路多了也不好，每次要從一個城鎮(zhèn)到另一個城鎮(zhèn)時，都有許多種道路方案可以選擇，而某些方案要比另一些方案行走的距離要短很多。這讓行人很困擾。

現(xiàn)在，已知起點和終點，請你計算出要從起點到終點，最短需要行走多少距離。

?

Input 本題目包含多組數(shù)據(jù)，請?zhí)幚淼轿募Y(jié)束。
每組數(shù)據(jù)第一行包含兩個正整數(shù)N和M(0<N<200,0<M<1000)，分別代表現(xiàn)有城鎮(zhèn)的數(shù)目和已修建的道路的數(shù)目。城鎮(zhèn)分別以0～N-1編號。
接下來是M行道路信息。每一行有三個整數(shù)A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城鎮(zhèn)A和城鎮(zhèn)B之間有一條長度為X的雙向道路。
再接下一行有兩個整數(shù)S,T(0<=S,T<N)，分別代表起點和終點。

?

Output 對于每組數(shù)據(jù)，請在一行里輸出最短需要行走的距離。如果不存在從S到T的路線，就輸出-1.

?

Sample Input 3 3 0 1 1 0 2 3 1 2 1 0 2 3 1 0 1 1 1 2

?

Sample Output 2 -1 注意：兩地之間可能有多條路。所以輸入時要去最小值。 View Code #include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <cstring>
#include <sstream>
#include <fstream>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <algorithm>

using namespace std;
//Constant Declaration
/*--------------------------*/
//#define LL long long
#define LL __int64
const int M=250;//最多點數(shù)
const int INF=1<<30;
const double EPS = 1e-11;
const double PI = acos(-1.0);
/*--------------------------*/
// some essential funtion
/*----------------------------------*/
void Swap(int &a,int &b){ int t=a;a=b;b=t; }
int Max(int a,int b){ return a>b?a:b; }
int Min(int a,int b){ return a<b?a:b; }
int Gcd(int a,int b){ while(b){b ^= a ^=b ^= a %= b;} return a; }
/*----------------------------------*/
//for (i = 0; i < n; i++)
/*----------------------------------*/

int d[M];//表示i到源點的最短距離
int g[M][M];//鄰接矩陣
bool used[M];//標記i是否被用過

void init(int n)
{
int i, j;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
g[i][j] = INF;//初始化圖沒有邊，默認為INF,為了一定更新
}
}
for (i = 0; i < n; i++)
{
d[i] = INF;
}

memset(used, false, sizeof(used));
}

int dijkstra(int star, int end, int n)//起點，終點，總點數(shù)(編號為1,2...n)
{
int min_num = 1;//最小值的位置
int i;
d[star] = 0;//起點到起點的最短距離為0，很重要的一步
for (int cnt = 0; cnt < n; cnt++)//注意別用while(n--),這樣會改變n的值。n次貪心
{
int min = INF;
for (i = 0; i < n; i++)
{
if (!used[i] && d[i] < min)
{
min = d[i];
min_num = i;
}
}

used[min_num] = 1;

//把d[min_num]作為中間點，對相鄰的點做松弛
for (i = 0; i < n; i++)
{
if (!used[i] && d[i] > d[min_num] + g[min_num][i])
{
d[i] = d[min_num] + g[min_num][i];
}
}

}
return d[end];
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
//int t, case1 = 0;
//scanf("%d", &t);
int n, m;
int i, j;
while (scanf("%d%d", &n, &m) != EOF)
{
init(n);
while (m--)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
g[b][a] = g[a][b] = Min(c, g[a][b]);//此題為無向圖
}
int star, end;
scanf("%d%d", &star, &end);
int ans = dijkstra(star, end, n);
if(INF == ans)
{
puts("-1");
}
else
{
printf("%d\n", ans);
}
}

return 0;
}

轉(zhuǎn)載于:https://www.cnblogs.com/qiufeihai/archive/2012/03/06/2382470.html

總結(jié)

以上是生活随笔為你收集整理的HDU 1874 畅通工程续的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。