﻿HDU 1874 畅通工程续(Floyd)-Ocrosoft

# 畅通工程续

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 46088    Accepted Submission(s): 17154

Problem Description

Input

Output

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
```

Author
linle

Solution

```#include <set>
#include <map>
#include <list>
#include <cmath>
#include <stack>
#include <queue>
#include <ctime>
#include <string>
#include <cstdio>
#include <vector>
#include <cctype>
#include <climits>
#include <sstream>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ms(a) memset(a,0,sizeof(a))
#define INF INT_MAX
#define MAXN 200+10
using namespace std;
int edge[MAXN][MAXN];
int main()
{
int n,m;
while(cin>>n>>m)
{
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)edge[i][j]=INF;
for(int i=1;i<=m;i++)
{
int u,v,w;
cin>>u>>v>>w;
if(edge[u][v]>w)edge[u][v]=edge[v][u]=w;
}
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
if(edge[i][k]<INF&&edge[k][j]<INF)
edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j]);
int S,T;
cin>>S>>T;
if(S==T)printf("0\n");
else printf("%d\n",edge[S][T]==INF?-1:edge[S][T]);
}
return 0;
}
```