| 3228K | 485MS | G++ | 2453B |
根据题意和测试用例知道这是一个求次短路径的题目。次短路径，就是比最短路径长那么一丢丢的路径，而题中又是要求从一点到指定点的次短路径，果断Dijkstra。
R (1 ≤ R ≤ 100,000，N (1 ≤ N ≤ 5000) ，length D (1 ≤ D ≤ 5000)，所以我用链式向前星方法存储，这个不知道的点这里(我转载别人的，讲的挺详细)。
用一个二维数组dist[MAXN][2],去记录i->j的最短路径和次短路径，第二维是0表示当期拿记录最短边，是1表示当前记录次短边。思路是这样，dist初始值为INF，当if(!vis[j][0] && dis[j][0] < MIN)，即找到最短边，标记下来;如果 else if(!vis[j][1] && dis[j][1] < MIN)，则是次短边，标记下来。所后进行松弛操作。。。。
/*************************************************************************
> File Name: poj3255.cpp
> Author: YeGuoSheng
> Description:
给定n个点和需要到达的点编号
问从1号点到目标点的次短路径
> Created Time: 2019年07月21日 星期日 16时40分46秒
************************************************************************/ #include<iostream>
#include<stdio.h>
#include<cstring>
#include<cmath>
#include<stack>
#include<map>
#include<set>
#include<list>
#include<queue>
#include<string>
#include<algorithm>
#include<iomanip>
#define INF 0x3f3f3f3f
#define MAXN 50010 struct node
{
int v;
int next;
int w;
}edges[MAXN<<]; int head[MAXN];
int cnt;
int dis[MAXN][];//dist [i][0]：1 最短路径 ,dist[i][1]次短路径
bool vis[MAXN][];//vis[i][0]：1 表示到结点i的最短路径已找到，vis[i][1]表示到结点i的次短路径已找到
int n,m; void add(int u,int v,int w)//链式向前星存储
{
edges[++cnt].v=v;
edges[cnt].w=w;
edges[cnt].next=head[u];
head[u]=cnt;
} void dijkstra(int s)
{
for(int i=;i <= n;i++)
{
dis[i][]=dis[i][]= INF;//dist [i][0] 最短路径 ,dist[i][1]次短路径
vis[i][]=vis[i][]= ;
}
dis[s][] = ;
for(int i = ;i < n*;i++)
{
int MIN = INF;
int k = ;
int flag = ;
for(int j = ;j <= n;j++)
{
if(!vis[j][] && dis[j][] < MIN)
{
MIN=dis[j][];//找到最小边 将点标记
k=j;
flag = ;
}
else if(!vis[j][] && dis[j][] < MIN)//否则找到的就是次短边
{
MIN=dis[j][];
k=j;
flag = ;
}
}
if(MIN == INF)break;//没找到 最短或次短路径
vis[k][flag]=;//标记到结点k的最小边或次短边已经找到
for(int j= head[k];j!=-;j=edges[j].next)
{
int v = edges[j].v;//第j条边的终点
int w = edges[j].w;//这条边的权重
if(MIN+w <= dis[v][])//小于最短边，更新最短边，同时最短边变为次短边
{
dis[v][] = dis[v][];//既然dis[v][0]有更小的，那么我先把原来的赋值给dis[v][1]
dis[v][] = MIN+w;
}
else if(MIN+w <= dis[v][])//如果大于最短边，小于次短边，根新次短边
{
dis[v][] = MIN+w;
}
}
}
}
int main()
{
memset(head,-,sizeof(head));
cnt = ;
scanf("%d%d",&n,&m);// n:目标结点, m：边的数幂
for(int i=;i<=m;i++)
{
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);
add(y,x,z);
}
dijkstra();
printf("%d\n",dis[n][]);
return ;
}