附加赛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;
}