频道栏目
首页 > 程序开发 > 软件开发 > 其他 > 正文
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.

Sample Input

3 3
1 2 1
1 3 1
2 3 1
3 2
1 2 1
1 3 2

Sample Output

2
-1

水题:有n个城市,问按顺序从1到n的最短路径。

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;  
}
点击复制链接 与好友分享!回本站首页
上一篇:activiti 快速入门--一个比较不错的操作工具类
下一篇:模拟 Spring Bean 生命周期
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站