HDU 1874 畅通公程续 （最短路 水）
生活随笔
收集整理的這篇文章主要介紹了
HDU 1874 畅通公程续 （最短路 水）
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
Problem Description
某省自從實行了非常多年的暢通project計劃后，最終修建了非常多路。只是路多了也不好，每次要從一個城鎮到還有一個城鎮時，都有很多種道路方案能夠選擇，而某些方案要比還有一些方案行走的距離要短非常多。這讓行人非常困擾。
如今，已知起點和終點，請你計算出要從起點到終點，最短須要行走多少距離。
如今，已知起點和終點，請你計算出要從起點到終點，最短須要行走多少距離。
Input
本題目包括多組數據，請處理到文件結束。
每組數據第一行包括兩個正整數N和M(0<N<200,0<M<1000)，分別代表現有城鎮的數目和已修建的道路的數目。城鎮分別以0～N-1編號。
接下來是M行道路信息。每一行有三個整數A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城鎮A和城鎮B之間有一條長度為X的雙向道路。
再接下一行有兩個整數S,T(0<=S,T<N)，分別代表起點和終點。
每組數據第一行包括兩個正整數N和M(0<N<200,0<M<1000)，分別代表現有城鎮的數目和已修建的道路的數目。城鎮分別以0～N-1編號。
接下來是M行道路信息。每一行有三個整數A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城鎮A和城鎮B之間有一條長度為X的雙向道路。
再接下一行有兩個整數S,T(0<=S,T<N)，分別代表起點和終點。
Output
對于每組數據，請在一行里輸出最短須要行走的距離。假設不存在從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
迪科斯徹的模板題。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <stack>
#define lson o<<1, l, m
#define rson o<<1|1, m+1, r
using namespace std;
typedef long long LL;
const int maxn = 205;
const int MAX = 0x3f3f3f3f;
const int mod = 1000000007;
int m, n, st, en;
int g[205][205], dij[205], vis[205];
void DIJ() {
memset(dij, MAX, sizeof(dij));
memset(vis, 0, sizeof(vis));
dij[st] = 0;
for(int i = 0; i < n; i++){
int tmp = MAX, pos;
for(int j = 0; j < n; j++)
if(vis[j] == 0 && dij[j] < tmp) {
tmp = dij[j];
pos = j;
}
vis[pos] = 1;
for(int j = 0; j < n; j++)
if(vis[j] == 0 &&dij[pos] + g[pos][j] < dij[j]) dij[j] = dij[pos] + g[pos][j];
}
}
int main()
{
while(~scanf("%d%d", &n, &m)) {
memset(g, MAX, sizeof(g));
for(int i = 1; i <= m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c) ;
if(c > g[a][b]) continue;
g[a][b] = g[b][a] = c;
}
scanf("%d%d", &st, &en);
DIJ();
if(vis[en]) printf("%d\n", dij[en]);
else printf("-1\n");
}
return 0;
}
總結
以上是生活随笔為你收集整理的HDU 1874 畅通公程续 （最短路 水）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： open-falcon之agent
- 下一篇： 迈腾GTE无端亮发动机故障？