链接：http://wikioi.com/problem/1021/
这题挺有意思的，虽然比较水，但是让我想起来那次百度or腾讯的一道最大流的题目，很给力，也是对最后找边进行优化，不过这题比那题简单多了，找出最短路，然后对最短路上的变进行一下标记，最后找边的时候只招最短路上的边就可以了。
代码：
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#define loop(s,i,n) for(i = s;i < n;i++)
#define cl(a,b) memset(a,b,sizeof(a))
using namespace std;
int vis[],pre[],dis[];
struct edge
{
int u,v,w,next,id;
}edges[*]; int head[];
int cnt;
void addedge(int u,int v,int w,int id)
{
edges[cnt].u = u;
edges[cnt].v = v;
edges[cnt].w = w;
edges[cnt].id = id;
edges[cnt].next = head[u];
head[u] = cnt;
cnt++;
}
void init()
{
cnt = ;
cl(head,-);
}
int spfa(int n,int flag)
{
int i;
loop(,i,n+)
vis[i] = ,dis[i] = *+;
queue<int> q;
q.push();
vis[] = ;
dis[] = ;
pre[] = -;
while(!q.empty())
{
int u,v;
u = q.front();
q.pop();
vis[u] = ;
for(int i = head[u];i != -;i = edges[i].next)
{
if(edges[i].id == flag)
continue;
v= edges[i].v;
if(dis[v] > edges[i].w+dis[u])
{
dis[v] = edges[i].w+dis[u];
pre[v] = i;
if(!vis[v])
q.push(v),vis[v] = ;
}
}
}
return dis[n];
}
int main()
{
int n,m;
scanf("%d %d",&n,&m);
{
int i,j;
int u,v,w;
init();
for(i = ;i <= m;i++)
scanf("%d %d %d",&u,&v,&w),addedge(u,v,w,i),addedge(v,u,w,i);
int ans;
ans = -;
spfa(n,);
for(i = pre[n];i != - ;i = pre[edges[i].u])
{
int leap;
leap = edges[i].id;
ans = max(ans,spfa(n,leap));
}
printf("%d\n",ans);
}
return ;
}