本文主要是介绍HDU 1874畅通工程续，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
畅通工程续
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 31641 Accepted Submission(s): 11558
现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
每组数据第一行包含两个正整数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)，分别代表起点和终点。
3 3 0 1 1 0 2 3 1 2 1 0 2 3 1 0 1 1 1 2
2 -1
1A基本已经形成模板#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<vector>
#include<cmath>
#include<stdlib.h>
#include<iomanip>
#include<list>
#include<deque>
#include<map>
#include <stdio.h>
#include <queue>
#define maxn 10000+5
#define ull unsigned long long
#define ll long long
#define reP(i,n) for(i=1;i<=n;i++)
#define rep(i,n) for(i=0;i<n;i++)
#define cle(a) memset(a,0,sizeof(a))
#define mod 90001
#define PI 3.141592657
const ull inf = 1LL << 61;
const double eps=1e-5;
using namespace std;
const int INF=9999999;
bool cmp(int a,int b){
return a>b;
}
int n,m;
int edge[210][210];
int vis[210];
int lowcost[210];
void Dj(int s,int t)
{
cle(vis);
vis[s]=1;
for(int i=0;i<n;i++)
lowcost[i]=edge[s][i];
int Min,k;
while(1)
{
Min=INF;
for(int j=0;j<n;j++)
{
if(lowcost[j]<Min&&!vis[j])
{
Min=lowcost[j];k=j;
}
}
vis[k]=1;
if(Min==INF)break;
for(int j=0;j<n;j++)
{
if(lowcost[j]>lowcost[k]+edge[k][j])
lowcost[j]=lowcost[k]+edge[k][j];
}
}
if(lowcost[t]==INF)cout<<-1<<endl;
else cout<<lowcost[t]<<endl;
}
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int a,b,c;
int s,t;
while(cin>>n>>m)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
edge[i][j]=INF;
}
edge[i][i]=0;
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(c<edge[a][b])
{
edge[a][b]=c;edge[b][a]=c;
}
}
cin>>s>>t;
Dj(s,t);
}
return 0;
}
这篇关于HDU 1874畅通工程续的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
