UOJ Logo Dream_zhc的博客

博客

8.20附加赛 T1题解(蒟蒻发布)

2018-08-21 10:03:20 By Dream_zhc

附加赛T1题解

首先,解释一下题目大意。题目要求,在n个点、m条边的无向图中求n+m条最短路径 前n条最短路径,第i条需要经过第i个点,后m条最短路径,第i条需要经过第i条边。

注意:

必须要经过某个点的最短路,例如要经过x点,我们可以求1到x的最短路径,再 求x到n的最短路径。为什么?显然因为要经过x点,所以我们把路径分为两部分,前半 部分为1到x的路程,是最短路径,后半部分为x到n的路程,也是最短路径。

注意:

必须要经过某条边的最短路,例如要经过边y,连接的两个点分别为u,v。我们 照葫芦画瓢,先求1到u的最短路,再求v到n的最短路,然后加上边y的权值。这种做法 看上去十分正确(但我比赛交上去,爆0了)。为什么呢?后来才想到,因为这次不是 经过一个点了,而是经过一条边,也就是说,先经过u点和先经过v点是没有影响的, 所以我们就多出了一种方案,即1先到v的最短路,经过边,再u到n的最短路。我们将 两种方案取一个min值即可。 最后,题目两种要求全都转化成了最短路。我们nlogn(堆优化dijkstra)跑一下1和n到 其他点的单源最短路,这道题目就做完了。(本人已A,放心食用,如有错误,请指出 并告知。谢谢)

代码:

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<queue>
#define PAIR pair<int,int>
#define N 100010
#define M 200010
#define MAXN 1000010
#define mk(a,b) make_pair(a,b)
using namespace std;
int dis[N],dis1[N];
struct node{
    int to,next1,w;
}e[M*2];
priority_queue < PAIR ,vector< PAIR >,greater< PAIR > > q;
int ww[M*2],uu[M*2],vv[M*2],n,m,si,h[N];
void Add(int u,int v,int w)
{
    e[++si].to=v,e[si].next1=h[u],e[si].w=w,h[u]=si;
}//邻接表(链式前向星)
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
      dis[i]=MAXN,dis1[i]=MAXN;//预处理
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        Add(u,v,w);Add(v,u,w);
        uu[i]=u;
        vv[i]=v;
        ww[i]=w;//存下边的信息以便后面输出
    }
    dis[1]=0;dis1[n]=0;
    q.push(mk(dis[1],1)); //堆优化一下
    while(!q.empty())
    {
        int x=q.top().second;
        q.pop();
        for(int i=h[x];i;i=e[i].next1)
        {
            int y=e[i].to;
            if(dis[y]>dis[x]+e[i].w)
            {
                dis[y]=dis[x]+e[i].w;
                q.push(mk(dis[y],y));
            }
        }
    }
    q.push(mk(dis1[n],n)); 
    while(!q.empty())
    {
        int x=q.top().second;
        q.pop();
        for(int i=h[x];i;i=e[i].next1)
        {
            int y=e[i].to;
            if(dis1[y]>dis1[x]+e[i].w)
            {
                dis1[y]=dis1[x]+e[i].w;
                q.push(mk(dis1[y],y));
            }
        }
    }//代码拙劣,大家可以写自定义函数的,我大概是直接复制了
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",dis[i]+dis1[i]);
    }
    int t;
    for(int i=1;i<=m;i++)
    {
        t=min(dis[uu[i]]+dis1[vv[i]],dis[vv[i]]+dis1[uu[i]]);//注意取min!! 
        printf("%d\n",ww[i]+t);
    }
    return 0;
}

评论

gaolinxiang
前排顶!
  • 2018-08-21 10:08:04