题目
http://www.joyoi.cn/problem/tyvj-1450
题目大意
求最短路和次短路
解题思路
当p=1时，显然是最短路。
当p=2时：
首先以1和n为起点做一遍单源最短路，然后枚举每一条边(x,y)，求出起点到x+终点到y+边(x,y)权值之和，若不等于1~n最短路长度则更新ans。
预期得分100分
代码
#include<cstdio>
#include<queue>
#include<string>
#include<cstring>
#define rr register
using namespace std;
const int N=10010,M=50001;
bool vis[N],p;
int n,m,cnt,head[N],dis[N],pre[N],ans=2147483647;
queue<int> q;
struct node{
int x,y,z,next;
}a[M<<1];
void add(int x,int y,int z){a[++cnt]=(node){x,y,z,head[x]}; head[x]=cnt;}
int read(){
int p=0; char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) p=(p<<3)+(p<<1)+c-48,c=getchar();
return p;
}
void spfa(){
memset(dis,127/2,sizeof(dis));
q.push(1);
vis[1]=1; dis[1]=0;
while (!q.empty()){
int x=q.front(); q.pop();
for (rr int i=head[x];i;i=a[i].next){
int y=a[i].y;
if (a[i].z+dis[x]<dis[y]) {
dis[y]=dis[x]+a[i].z;
if (!vis[y]) q.push(y),vis[y]=1;
}
}
vis[x]=0;
}
}
void spfaa(){
memset(pre,127/2,sizeof(pre));
q.push(n);
vis[n]=1; pre[n]=0;
while (!q.empty()){
int x=q.front(); q.pop();
for (rr int i=head[x];i;i=a[i].next){
int y=a[i].y;
if (a[i].z+pre[x]<pre[y]) {
pre[y]=pre[x]+a[i].z;
if (!vis[y]) q.push(y),vis[y]=1;
}
}
vis[x]=0;
}
}
int main(){
n=read(),m=read();
int x,y,z;
for (rr int i=1;i<=m;i++){
x=read(),y=read(),z=read();
add(x,y,z),add(y,x,z);
}
p=read();
spfa(); spfaa();
if (p==0) return 0&printf("%d",dis[n]);
for (rr int i=1;i<=cnt;i++){
int x=a[i].x,y=a[i].y;
int e=dis[x]+pre[y]+a[i].z;
if (e!=dis[n]&&e<ans) ans=e;
}
printf("%d",ans);
}