UVA11374 Airport Express

客官°小女子只卖身不卖艺 2023-06-04 07:59 25阅读 0赞

[**题目链接**][Link 1]

**在刘汝佳的那本书上看到了这道题，思路：先预处理出起点到所有点以及终点到所有点的最短路径，然后就是枚举所有的商务边，因为只能有一条商务边，所以最优的路径肯定要么就是起点->商务边起点->商务边终点->终点，要么就是直接起点->终点。时间复杂度为预处理的mlogn加上k次枚举。最后还要递归输出路径。**

**代码如下，UVA的输出有毒，一直过不了，但肯定是对的。**

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

//不知道是怎么回事，可能是输出格式的问题。 
    #include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e6+7;
    struct node{
        int nxt,to,val;
    }edge[maxn*3];
    int head[maxn],cnt;
    int dis[maxn],dis1[maxn];
    int ans;
    inline void add(int x,int y,int v){
        edge[++cnt].nxt=head[x];
        edge[cnt].to=y;
        edge[cnt].val=v;
        head[x]=cnt;
    }
    int n,s,e,m,k,x,y,z;
    int o,p,t;
    bool vis[maxn],vis1[maxn];
    int pre1[maxn],pre2[maxn];
    int ljb;
    priority_queue< pair<int,int> >q;
    inline void dijkstra(int x){
        memset(dis,0x3f3f3f3f,sizeof(dis));
        q.push(make_pair(0,x));
        dis[x]=0;
        while(q.size()!=0){
            int u=q.top().second;
            q.pop();
            if(vis[u]) continue;
            vis[u]=true;
            for(int i=head[u];i;i=edge[i].nxt){
                int s=edge[i].to;
                if(dis[u]+edge[i].val<dis[s]){
                    pre1[s]=u;
                    dis[s]=dis[u]+edge[i].val;
                    q.push(make_pair(-dis[s],s));
                }
            }
        }
    }
    priority_queue< pair<int,int> >q1;
    inline void dijkstra2(int x){
        memset(dis1,0x3f3f3f3f,sizeof(dis1));
        q1.push(make_pair(0,x));
        dis1[x]=0;
        while(q1.size()!=0){
            int u=q1.top().second;
            q1.pop();
            if(vis1[u]) continue;
            vis1[u]=true;
            for(int i=head[u];i;i=edge[i].nxt){
                int v=edge[i].to;
                if(dis1[v]>dis1[u]+edge[i].val){
                    pre2[v]=u;
                    dis1[v]=dis1[u]+edge[i].val;
                    q1.push(make_pair(-dis1[v],v));
                }
            }
        }
    }
    void print1(int x){
        if(x==s){
            printf("%d",x);
            return;
        } 
        print1(pre1[x]);
        printf(" %d",x);
    }
    void print2(int x){
        if(!x) return;
        printf(" %d",x);
        print2(pre2[x]);
    }
    int main(){
        while(scanf("%d%d%d",&n,&s,&e)!=EOF){
            if(ljb==1) printf("\n"),ljb=0;
            memset(edge,0,sizeof(edge));
            memset(head,0,sizeof(head));
            memset(vis,0,sizeof(vis));
            memset(vis1,0,sizeof(vis1));
            memset(pre2,0,sizeof(pre2));
            memset(pre1,0,sizeof(pre1));
            cnt=0;
            scanf("%d",&m);
            for(register int i=1;i<=m;i++){
                scanf("%d%d%d",&x,&y,&z);
                add(x,y,z);add(y,x,z);
            }
            dijkstra(s);
            ans=dis[e];
            dijkstra2(e);
            scanf("%d",&k);
            int l=0,r=0;
            for(register int i=1;i<=k;i++){
                scanf("%d%d%d",&o,&p,&t);
                int s1=dis[o]+dis1[p]+t;
                int s2=dis[p]+dis1[o]+t;
                if(ans>s1){
                    ans=s1;
                    l=o;r=p;
                } 
                if(ans>s2){
                    ans=s2;
                    l=p;r=o;
                }
            }
            if(l==0){
                print1(s);
                printf("\nTicket Not Used\n%d\n",ans);
            }
            else{
                print1(l);print2(r);
                printf("\n%d\n%d\n",l,ans);
            }
            ljb=1;
        }
        return 0;
    }

转载于:https://www.cnblogs.com/LJB666/p/11332574.html

[Link 1]: https://www.luogu.org/problem/UVA11374
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/b29a3956902a41fd81fa25968d3e6775.png