uva 11374/Airport Express

In a small city called Iokh, a train service,

Airport-Expresstakes residents to the airport more quickly than other trans-ports. There are two types of trains in Airport-Express,theEconomy-XpressandtheCommercialXpress. Theytravel at different speeds, take different routes and have dif-ferent costs.Jason is going to the airport to meet his friend. He wantto take the Commercial-Xpress which is supposed to be faster,but he doesn't have enough money. Luckily he has a ticketor the Commercial-Xpress which cantakehimonestationforward. If he used the ticket wisely, he might end up savinga lot of time. However, choosing the best time to use theticket is not easy for him.Jasonnow seeks your help. The routes of the two typesof trains are given. Please write a program to nd the bestroute to the destination. The program should also tellwhen the ticket should be used.InputThe input consists of several test cases. Consecutive cases are separated by a blank line.The rst line of each case contains 3integers, namely

number of stations, the starting point and where the airport is located respectively.

There is an integer

M

(1

M

1000) representing the number of connections between the stations

of the Economy-Xpress. The next

M

lines give the information of the routes of the Economy-Xpress.

Each consists of three integers

X

Y

and

Z

(

X;Y

N;

1

100). This means

X

and

Y

are

connected and it takes

Z

minutes to travel between these two stations.

The next line is another integer

K

(1

K

1000) representing the number of connections between

the stations of the Commercial-Xpress. The next

K

lines contain the information of the Commercial-

Xpress in the same format as that of the Economy-Xpress.

All connections are bi-directional. You may assume that there is exactly one optimal route to the

airport. There might be cases where you MUST use your ticket in order to reach the airport.

Output

For each case, you should rst list the number of stations which Jason would visit in order. On the

next line, output `

Ticket Not Used

' if you decided NOT to use the ticket; otherwise, state the station

where Jason should get on the train of Commercial-Xpress. Finally, print the total time for the journey

on the last line. Consecutive sets of output must be separated by a blank line.

SampleInput

4 1 4

4

1 2 2

1 3 3

2 4 4

3 4 5

1

2 4 3

SampleOutput

1 2 4

2

5

思路：因为只能用一条特殊边，所以就一条一条的枚举吧，要一条特殊边的最短路就是这条边的两个顶点到起点或者终点的最短路相加在加上这条特殊边，所以用dijkstra算出s，e到每个顶点的最短路在枚举就行了，gay的就是输出格式。

<span style="font-size:18px;">#include <iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
#define big 99999999
using namespace std;
int *d,*p,n,s,e,ds[505],de[505],ps[505],pe[505],g[505][505],vis[505];
void dist(int x)
{
    if(x==s) d=ds,p=ps;
    else d=de,p=pe;
    for(int i=1; i<=n; i++)
        d[i]=big;
    d[x]=p[x]=0;
    memset(vis,0,sizeof(vis));
    while(1)
    {
        int v=-1,M=big;
        for(int i=1; i<=n; i++)
        {
            if(M>d[i]&&!vis[i])
            {
                v=i,M=d[i];
            }
        }
        if(v==-1) break;
        vis[v]=1;
        for(int i=1; i<=n; i++)
        {
            if(!vis[i]&&d[i]>d[v]+g[v][i])
            {
                d[i]=d[v]+g[v][i];
                p[i]=v;
            }
        }
    }
}
void print(int x)
{
    if(ps[x]) print(ps[x]);
    if(x==e) printf("%d",e);
    else
    printf("%d ",x);
}
int main()
{
    int m,x,y,l,v,u,ls,cc=0;
    while(scanf("%d %d %d",&n,&s,&e)!=EOF)
    {
        if(cc++)printf("\n");
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                g[i][j]=big;
        scanf("%d",&m);
        for(int i=1; i<=m; i++)
        {
            scanf("%d %d %d",&x,&y,&l);
            g[x][y]=g[y][x]=l;
        }
        memset(ps,0,sizeof(ps));
        memset(pe,0,sizeof(pe));
        dist(s);
        dist(e);
        scanf("%d",&m);
        int dz=big,sum=big,q=s,p=e;
        for(int i=1; i<=m; i++)
        {
            scanf("%d %d %d",&v,&u,&ls);
            if(ps[v]!=u&&pe[u]!=v)
                dz=ds[v]+de[u]+ls;
            if(dz<sum)
            {
                sum=dz;
                q=v,p=u;
            }
            if(ps[u]!=v&&pe[v]!=u)
                dz=ds[u]+de[v]+ls;
            if(dz<sum)
            {
                sum=dz;
                q=u,p=v;
            }
        }
        if(sum>=ds[e])
        {
            print(e);
            sum=ds[e];
            printf("\n");
            q=0;
        }
        else
        {
            print(q);
            int j=p;
            while(1)
            {
                if(j==e) break;
                printf("%d ",j);
                j=pe[j];
            }
            printf("%d\n",e);
        }
        if(q)
            printf("%d\n",q);
        else
            printf("Ticket Not Used\n");
        printf("%d\n",sum);
    }
    return 0;
}
</span>