首页 > ACM题库 > HDU-杭电 > hdu 2388 Playground Hideout-最短路径[解题报告]C++
2014
01-05

hdu 2388 Playground Hideout-最短路径[解题报告]C++

Playground Hideout

问题描述 :

Little Timmy likes playgrounds, especially those with complicated constructions of wooden towers interconnected with plank bridges or ropes, with slides and rope-ladders. He could play on his favourite playground for days, if only his parents let him. Sooner or later they decide that it is time to go home. For their next trip to a playground Timmy has a plan: he will not simply let his father grab him, but climb to the highest platform of the most complex structure and hide there. His father will never be able to reach him there or at least it will give Timmy some extra time.
An adventure playground consists of several platforms. The difficulty of reaching a platform directly from ground level varies. In addition the different platforms are interconnected by “bridges” of different difficulty. There are connections that can be used a lot more easily in one direction than in the other, e.g. slides. Given a plan of an adventure playground you need to help Timmy find the platform that is most difficult to reach from ground level. The difficulty for a path in the adventure playground can be estimated as a sum of the difficulties of the connections used. The difficulty of reaching a platform is the difficulty of the least difficult path from ground level to the platform.

输入:

The input starts with a line containing a single integer n, the number of test cases. Each test case starts with a line containing two integers 1 <= p, c <= 10000, the number of platforms and connections respectively (we allow for large playgrounds). A line with p integers pi ∈ [0, 1000] follows, where pi is the difficulty of reaching platform i directly from ground-level. The next c lines each describe a connection between two platforms. They consist of four integers i, j, a, b; i < j, the zero-based index of the two connected
platforms and the difficulties a ∈[0, 1000] and b ∈ [0, 1000] of using the connection to get from pi to pj and from pj to pi respectively. There can be multiple connections between any two platforms.

输出:

The input starts with a line containing a single integer n, the number of test cases. Each test case starts with a line containing two integers 1 <= p, c <= 10000, the number of platforms and connections respectively (we allow for large playgrounds). A line with p integers pi ∈ [0, 1000] follows, where pi is the difficulty of reaching platform i directly from ground-level. The next c lines each describe a connection between two platforms. They consist of four integers i, j, a, b; i < j, the zero-based index of the two connected
platforms and the difficulties a ∈[0, 1000] and b ∈ [0, 1000] of using the connection to get from pi to pj and from pj to pi respectively. There can be multiple connections between any two platforms.

样例输入:

2
4 3
1 10 10 40
0 3 3 2
1 3 4 3
2 3 5 4
2 2
11 10
0 1 2 2
0 1 1 0

样例输出:

Scenario #1:
2

Scenario #2:
0

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int N = 10010;

struct node
{
    int v;
    int w;
    node(){};
    node(int x,int y):v(x),w(y){}
    bool operator <(const node &cp)const
    {
        return w > cp.w;
    }
};

vector<node>map[N];
priority_queue<node>que;
int dist[N],visit[N];
int n,m;


void input()
{
    scanf("%d%d",&n,&m);
    for(int i = 0;i <= n;i ++)
        map[i].clear();
    for(int i = 0;i < n;i ++)
        scanf("%d",&dist[i]);
    int u,v,a,b;
    while(m --)
    {
        scanf("%d%d%d%d",&u,&v,&a,&b);
        map[u].push_back(node(v,a));
        map[v].push_back(node(u,b));
    }
    for(int i = 0;i < n;i ++)
       visit[i] = 0;
    while(!que.empty())
          que.pop();
    for(int i = 0;i < n;i ++)
        que.push(node(i,dist[i]));
}

void solve()
{
    int x,y;
    while(!que.empty())
    {
        node tmp = que.top();
        que.pop();
        if(visit[tmp.v])
           continue;
        visit[tmp.v] = 1;
        dist[tmp.v] = tmp.w;
        for(int i = 0;i < map[tmp.v].size();i ++)
        {
            x = map[tmp.v][i].v;
            y = map[tmp.v][i].w;
            if(dist[x] > tmp.w+y)
            {
                dist[x] = tmp.w+y;
                que.push(node(x,dist[x]));
            }
        }
    }
}

int main()
{
    int t,cas=0;
    scanf("%d",&t);
    while(t --)
    {
        cas ++;
        input();
        solve();
        int ans = 0;
        for(int i = 1;i < n;i ++)
        {
            if(dist[ans] < dist[i])
                 ans = i;
        }
        printf("Scenario #%d:\n",cas);
        printf("%d\n\n",ans);
    }
    return 0;
}

 


  1. 这个麦田圈的出现,表明外星人飞行器对太阳的短暂的“修理”工作这时已经快结束了。这个图案表示的就是我们现在的太阳:经纬编织的部分表示的是太阳的核心;圆的边缘没有编织的部分表示太阳的环。中间直立的麦子表示在太阳上仍然有外星人飞行器守护在那里。