XTOJ 1245 Hamiltonian Path【伪最短路，水题】
2016-11-03 09:30:30         来源：AC_Dreameng

## Hamiltonian Path

Accepted : 41   Submit : 96
Time Limit : 2000 MS   Memory Limit : 65536 KB

# Hamiltonian Path

In ICPCCamp, there arencities andmdirected roads between cities. Thei-th road going from theai-th city to thebi-th city iscikilometers long. For each pair of cities(u,v), there can be more than one roads fromutov.

Bobo wants to make big news by solving the famousHamiltonian Pathproblem. That is, he would like to visit all thencities one by one so that the total distance travelled is minimized.

Formally, Bobo likes to findndistinctintegersp1,p2,…,pnto minimizew(p1,p2)+w(p2,p3)+?+w(pn?1,pn)wherew(x,y)is the length of road from thex-th city to they-th city.

## Input

The input contains at most30sets. For each set:

The first line contains2integersn,m(2≤n≤105,0≤m≤105).

Thei-th of the followingmlines contains3integersai,bi,ci(1≤ai).

## Output

For each set, an integer denotes the minimum total distance. If there exists no plan, output-1instead.

```3 3
1 2 1
1 3 1
2 3 1
3 2
1 2 1
1 3 2
```

## Sample Output

```2
-1```

AC代码：

```/**
* 行有余力，则来刷题！
* 博客链接：https://blog.csdn.net/hurmishine
*
*/

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e5;
const int INF=1e9;
int a[maxn];
int main()
{
//freopen("data.txt","r",stdin);
int n,m;
while(cin>>n>>m)
{
for(int i=2;i<=n;i++)
a[i]=INF;
int x,y,z;
while(m--)
{
scanf("%d%d%d",&x,&y,&z);
if(y-x==1&&z<a[y])
{
a[y]=z;
}
}
bool flag=true;
int ans=0;
for(int i=2;i<=n;i++)
{
if(a[i]<INF)
ans+=a[i];
else
{
flag=false;
break;
}
}
if(flag)
cout<<ans<<endl;
else
cout<<"-1"<<endl;
}
return 0;
}```