PAT 1111. Online Map (30)

6993 ワード

Input our current position and a destination, an online map canrecommend several paths. Now your job is to recommend two paths toyour user: one is the shortest, and the other is the fastest. It isguaranteed that a path exists for any request.
Input Specification:
Each input file contains one test case. For each case, the first linegives two positive integers N (2 <= N <= 500), and M, being the totalnumber of streets intersections on a map, and the number of streets,

Then M lines follow, each describes a street in theformat:

V1 V2 one-way length time
where V1 and V2 are the indices (from 0 to N-1) of the two ends of thestreet; one-way is 1 if the street is one-way from V1 to V2, or 0 ifnot; length is the length of the street; and time is the time taken topass the street.
Finally a pair of source and destination is given.
Output Specification:
For each case, first print the shortest path from the source to thedestination with distance D in the format:
Distance = D: source -> v1 -> ... -> destination
Then in the next line print the fastest path with total time T:
Time = T: source -> w1 -> ... -> destination
In case the shortest path is not unique, output the fastest one amongthe shortest paths, which is guaranteed to be unique. In case thefastest path is not unique, output the one that passes through thefewest intersections, which is guaranteed to be unique.
In case the shortest and the fastest paths are identical, print themin one line in the format:
Distance = D; Time = T: source -> u1 -> ... -> destination
原題
考え方:この問題は実は難しくなくて、面倒です.Dijkstraアルゴリズムを用いて最短経路を求めればよい.ただし、ここでの最短パスは、それぞれ最短長(同じ長さの場合は短い)と最短時間(同じ時間が経過する点が少ない)であり、この2つの量はprev配列を使用してパスを保存する必要があります.同じ長さの値に遭遇した場合は、2つのパスを作成して比較する必要があります.したがって、リカバリに注意する必要があります.

  int t=prev[i];
  ans=get_path(prev,i);
  prev[i]=v1;
  auto tt=get_path(prev,i);
  if(f2(tt)

正しいコード:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define INT_MAX       2147483647
#define repeat(n) for(int _i=0;_i>N>>M
#define get_v1(v) (v/500)
#define get_v2(v) (v%500)

int road[501][501]={0};
int len[501][501]={0},u_time[501][501]={0};
int dist1[501];
int src,dst;

typedef vector path;
int cal_time(const path& p)
{
    int s=0;
    for(int i=1;i0;i--)
        printf("%d -> ",p[i]);
    cout<dist[dst])
            assert(0);
        for(int i=0;idist[v1]+len[v1][i]){
                    dist[i]=dist[v1]+len[v1][i];
                    prev[i]=v1;
                }else if(dist[i]==dist[v1]+len[v1][i])
                {
                    int t=prev[i];
                    ans=get_path(prev,i);
                    prev[i]=v1;
                    auto tt=get_path(prev,i);
                    if(f2(tt)>v1>>v2>>one>>l>>t;
        road[v1][v2]=1;
        if(!one)
            road[v2][v1]=1;
        len[v1][v2]=len[v2][v1]=l;
        u_time[v1][v2]=u_time[v2][v1]=t;
        assert(v1>src>>dst;
    assert(N<501);
    //end input
    for(int i=0;i

vectorを使用してパスを格納し、setを使用して最小パスを取得します.構造がわかりやすい.なぜか問題があります.

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define INT_MAX       2147483647
#define repeat(n) for(int _i=0;_i>N>>M
#define get_v1(v) (v/500)
#define get_v2(v) (v%500)

int road[501][501]={0};
int len[501][501]={0},u_time[501][501]={0};
int dist1[501];
int src,dst;

typedef vector path;
int cal_time(const path& p)
{
    int s=0;
    for(int i=1;i ",p[i]);
    cout<bool
    {
        int l1=f1(v1),l2=f1(v2);
            if(l1==l2)
                return f2(v1) search(f);
    dist[src]=0;
    int visited[501]={0};
    int min_len=INT_MAX;
    path ans(1,src);
    search.insert(ans);
    while(!search.empty())
    {
        const auto p1=*search.begin();
        int v1=*p1.rbegin();
        visited[v1]=1;
        search.erase(search.begin());
        if(v1==dst)
        {
            return p1;
        }
        if(dist[v1]>dist[dst])
            break;
        for(int i=0;i=dist[v1]+len[v1][i]))
            {
                dist[i]=dist[v1]+len[v1][i];
                auto t=p1;
                t.push_back(i);
                search.insert(t);
            }
    }
    while(1) dist;
    assert(0);
    return ans;
}
int use_time[501];

int main()
{
#ifdef _DEBUG
    fstream cin("input.txt");
#endif
    (INPUT);
    for(int i=0;i>v1>>v2>>one>>l>>t;
        road[v1][v2]=1;
        if(!one)
            road[v2][v1]=1;
        len[v1][v2]=len[v2][v1]=l;
        u_time[v1][v2]=u_time[v2][v1]=t;
        assert(v1>src>>dst;
    assert(N<501);
    //end input
    for(int i=0;i

set-o vi検索履歴コマンド

Active Directoryでコンピューターを移動してから保護