Uva11374

因为商业线只能坐一次我们可以枚举做哪条。。先用两次迪杰斯特拉算法预处理出从起点到各个点的最短距离和终点到各个距离的最短路= =

假设d1[]存的是起点到其他点的距离，d2[]存的终点到其他点的距离。

那么总共的时间就是d1[a]+T(a,b)+d2[b];

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
const int inf=999999999;
const int maxn=100000;
using namespace std;
struct Edge
{
    int from,to,dist;
};
struct HeapNode
{
    int d,u;
    bool operator<(const HeapNode &rhs)const
    {
        return d>rhs.d;
    }
};
struct Dijkstra
{
     int  n,m;//点数个边数
     vector<Edge>edges;//边列表
     vector<int>G[maxn];//每个节点出发边的编号
     bool done[maxn];//标记是否访问过
     int d[maxn];//到源点的最短距离
     int p[maxn];//最短路额上一条边
     void init(int n)
     {
         this->n=n;
         for(int i=0;i<n;i++)
         G[i].clear();//清空邻接表
         edges.clear();//清空边表
     } 
     void addEdge(int from,int to,int dist)//若是无向图，每条无向图调用两次addEdges
     {
         edges.push_back((Edge){from,to,dist});
         m=edges.size();
         G[from].push_back(m-1);
     }
     void dijkstra(int s)//求s到所有点的距离
     {
         priority_queue<HeapNode>Q;
         for(int i=0;i<n;i++)
         d[i]=inf;
         d[s]=0;
         memset(done,0,sizeof(done));
         Q.push((HeapNode){0,s});
         while(!Q.empty())
         {
             HeapNode x=Q.top();
             Q.pop();
             int u=x.u;
             if(done[u])
             continue;
             done[u]=true;
             for(int i=0;i<G[u].size();i++)
             {
                 Edge &e=edges[G[u][i]];
                 if(d[e.to]>d[u]+e.dist)
                 {
                 d[e.to]=d[u]+e.dist;
                 p[e.to]=G[u][i];
                 Q.push((HeapNode){d[e.to],e.to});
                }
          }
     }
}
};
int d1[maxn],p1[maxn];
int d2[maxn],p2[maxn];
Dijkstra solve;
int N,S,E;
void print_fP(int k)
{
    if(k==S)
    {
    printf("%d",k+1);
    return ;
   }
   int t=p1[k];
   Edge& e=solve.edges[t];
   print_fP(e.from);
  printf(" %d",k+1);
} 
void print_fQ(int k)
{
    if(k==E)
    {
        printf(" %d",k+1);
        return ;
    }
    printf(" %d",k+1);
    int t=p2[k];
   Edge& e=solve.edges[t];
   print_fQ(e.from);    
}
int main()
{
    int count=0;
    while(scanf("%d%d%d",&N,&S,&E)!=EOF)
    {
        if(count++)
        printf("
");
        int M;
        solve.init(N);
        scanf("%d",&M);
        int x,y,z;
        while(M--)
        {
            scanf("%d%d%d",&x,&y,&z);
            x--;
            y--;
            solve.addEdge(x,y,z);
            solve.addEdge(y,x,z);
        }
        S--;
        E--;
        solve.dijkstra(S);
        for(int i=0;i<N;i++)
        {
            d1[i]=solve.d[i];
            p1[i]=solve.p[i]; 
        } 
        solve.dijkstra(E);
        for(int i=0;i<N;i++)
        {
            d2[i]=solve.d[i];
            p2[i]=solve.p[i];
        } 
        int ans=d1[E];
        int k;
        scanf("%d",&k);
        int a,b,c;
        int px=-1,py=-1;
        while(k--)
        {
            scanf("%d %d %d",&a,&b,&c);
            a--,b--;
            if(ans>d1[a]+c+d2[b])
            {
                ans=d1[a]+c+d2[b];
                px=a;
                py=b;
            }
            if(ans>d1[b]+d2[a]+c)
            {
                ans=d1[b]+c+d2[a];
                px=b;
                py=a;    
            }
        }
        if(px==-1)
        {
            print_fP(E);
            printf("
");
            printf("Ticket Not Used
");
            printf("%d
",ans);
        }
        else
        {
            print_fP(px);
            print_fQ(py);
            printf("
");
            printf("%d
",px+1);
            printf("%d
",ans); 
        }
    }
    return 0;
}