首页 > ACM题库 > HDU-杭电 > HDU 4479-Shortest path-图-[解题报告]HOJ
2015
07-16

HDU 4479-Shortest path-图-[解题报告]HOJ

Shortest path

问题描述 :

  There are N cities (marked by 1, 2, …, N) and M bidirectional roads in the kingdom. There may be several roads between any two cities, but there is not any road connects the same city.
Your task is to find a shortest path from city 1 to city N, and the lengths of the edges you passed by must be strictly in increasing order.

输入:

  There is an integer T (1 <= T <= 500) in the first line, indicates that there are T test cases in total.
  For each test case, there are two integers N (2 <= N <= 10000) and M (1 <= M <= 50000), which have the same meaning as above. Then there are M lines, and there are three integers x (1 <= x <= N), y (1 <= y <= N), and z (1 <= z <= 10000000) in each line, indicate there is a bidirectional road between city x and city y.
   There are at most ten test cases that satisfy that N > 200 or M > 1000.

输出:

  There is an integer T (1 <= T <= 500) in the first line, indicates that there are T test cases in total.
  For each test case, there are two integers N (2 <= N <= 10000) and M (1 <= M <= 50000), which have the same meaning as above. Then there are M lines, and there are three integers x (1 <= x <= N), y (1 <= y <= N), and z (1 <= z <= 10000000) in each line, indicate there is a bidirectional road between city x and city y.
   There are at most ten test cases that satisfy that N > 200 or M > 1000.

样例输入:

4
4 6
1 2 1
1 2 2
2 3 3
2 3 1
3 4 2
4 3 6
3 2
1 2 1
2 3 1
3 1
1 2 1
2 2
2 1 1
1 2 2

样例输出:

10
No answer
No answer
1

题意:求最短路,要求每一次走的路都比上一次的长。

思路:把所有边排序,然后从短到长的顺序找最短路,相同长度的同时考虑。。

机组数据:

3
5 5
1 2 1
2 3 2
3 4 3
1 4 4
4 5 4
5 5
1 2 2
2 3 3
3 4 4
1 4 5
4 5 5
5 5
1 2 2
2 3 3
3 4 4
1 4 5
4 5 6

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <stack>
#include <iostream>
using namespace std;
#define LL long long
const int N = 10009;
const int M = 100009;
const LL INF = 0x3f3f3f3f3f3f3f3f;
struct load{
    int f,t,dis;
    bool operator<(const load t)const{
        return dis<t.dis;
    }
} ld[M];
int n,m;
int fa[N];
LL dis[N];
int v[N];
LL vdis[N];
void oper(int st,int len)
{
    int cnt=  0,l,r,d;
    for(int i=0;i<len;i++)
    {
        l = ld[i+st].f,r= ld[st+i].t,d = ld[st+i].dis;
        if(fa[l]&&dis[r]>d+dis[l])
        {
            v[cnt] = r;
            vdis[cnt]= d+dis[l];
            cnt++;
        }
        if(fa[r]&&dis[l]>d+dis[r])
        {
            v[cnt] = l;
            vdis[cnt] = d+dis[r];
            cnt++;
        }
    }
    for(int i=0;i<cnt;i++)
    {
        dis[v[i]] = min(dis[v[i]],vdis[i]);
        fa[v[i]] = 1;
    }
}
void solve()
{
    memset(fa,0,sizeof(fa));
    for(int i=0;i<=n;i++) dis[i] = INF;
    dis[1] = 0;
    fa[1] = 1;
    for(int i=0;i<m;)
    {
        int j;
        for(j=i+1;j<m;j++)
        {
            if(ld[j].dis!=ld[i].dis) break;
        }
        oper(i,j-i);
        i = j;
    }
    if(dis[n]!=INF)
    cout<<dis[n]<<endl;
    else printf("No answer\n");
}
int main()
{
    freopen("in.txt","r",stdin);
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%d%d",&n,&m);
        for(int i=0;i<m;i++)
        scanf("%d%d%d",&ld[i].f,&ld[i].t,&ld[i].dis);
        sort(ld,ld+m);
        solve();
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/binwin20/article/details/8296416