题目

题目描述

      众所周知，GF同学喜欢打dota，而且打得非常好。今天GF和Spartan同学进行了一场大战。现在GF拿到一张地图，地图上一共有n个地点，GF的英雄处于1号点，Spartan的基地位于n号点，GF要尽快地选择较短的路线让他的英雄去虐掉Spartan的基地。但是Spartan早就料到了这一点，他有可能会开挂(BS~)使用一种特别的魔法，一旦GF所走的路线的总长度等于最短路的总长度时，GF的英雄就要和这种魔法纠缠不休。这时GF就不得不选择非最短的路线。现在请你替GF进行规划。

对于描述的解释与提醒：

    1.无向路径，花费时间当然为非负值。

    2.对于本题中非最短路线的定义：不管采取任何迂回、改道方式，只要GF所走的路线总长度不等于1到n最短路的总长度时，就算做一条非最短的路线。

    3.保证1~n有路可走。

输入

第一行为n，m(表示一共有m条路径) 

接下来m行，每行3个整数a，b，c，表示编号为a,b的点之间连着一条花费时间为c的无向路径。 

接下来一行有一个整数p，p=0表示Spartan没有开挂使用这种魔法，p=1则表示使用了。

输出

所花费的最短时间t，数据保证一定可以到达n。

输入样例复制

样例输入1： 5 5 1 2 1 1 3 2 3 5 2 2 4 3 4 5 1 0 样例输入2： 5 5 1 2 1 1 3 2 3 5 2 2 4 3 4 5 1 1

输出样例复制

样例输出1： 4 样例输出2： 5

说明

对于50%的数据，1<=n,m<=5000 

对于70%的数据，1<=n<=10000, 1<=m<=50000,p=0, 

对于100%的数据，1<=n<=10000, 1<=m<=50000,p=1 

无向图，花费时间c>=0 

 

分析

• 很明显一个spfa就好了

• 那我们如何求次短路呢
• 我们可以枚举每一段路
• 做两次spfa
• 然后枚举每一条边(x,y)，求出起点到x+终点到y+边(x,y)权值之和，若不等于1~n最短路长度则更新ans。 预期得分100分

    spfa pop之后一定要放回零

代码

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 int map[10010][10010]; 7 int n,m; 8 vector 
         
           f[10010]; 9 int vis[10010],dis[10010],aa[50010],bb[50010],cc[50010],diss[10010];10 queue 
          
            q,qq;11 void spfa()12 {13 vis[1]=1; dis[1]=0; q.push(1);14 while (!q.empty())15 {16 int x=q.front(); q.pop(); vis[x]=0; 17 for (int i=0;i
           
            >n>>m;58 for (int i=1,a,b,c;i<=m;i++)59 {60 cin>>a>>b>>c;61 aa[i]=a;62 bb[i]=b;63 cc[i]=c;64 f[a].push_back(b);65 f[b].push_back(a);66 map[a][b]=c;67 map[b][a]=c;68 }69 int p;70 cin>>p;71 memset(dis,0x3f,sizeof(dis));72 spfa();73 int minn=dis[n];74 if (p==0) {75 cout<