分析：
我一开始想了一个自己都可以hack掉的算法：
先来一个朴素spfa
之后循环与终点相连的所有边，
到达终点的距离就是dis[way[i].y]+way[i].v
统计最小的路径和次小的路径，输出答案
竟然过掉了6个点
然后我就暴力搜索，T了7个点，STO
好，我们来正经的
于是我又想了一个做法，每个点都统计一下到达该点的最小距离和次小距离
但这好像不大现实
后来我才发现，这是一道次短路的裸题
又可以学习一种新算法了
具体的做法引用一下BYVOID大牛文章里的一段话：
我们要对一个有向赋权图(无向图每条边可以看作两条相反的有向边)
的顶点S到T之间求次短路径，首先应求出S的单源最短路径
遍历有向图，标记出可以在最短路径上的边，加入集合K
然后枚举删除集合K中每条边，求从S到T的最短路径，
记录每次求出的路径长度值，其最小值就是次短路径的长度
在这里我们认为次短路径长度可以等于最短路径长度，
如果相等，也可以看作是从S到T有不止一条最短路径
如果我们规定求从S到T**大于最短路径长度**的次短路径，
则答案就是每次删边后大于原最短路径的S到T的最短路径长度的最小值
成功AC
这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int INF=0x33333333;
const int N=10001;
int s,t,n,m;
struct node{
int x,y,nxt,v;
};
node way[N<<2];
int st[N],tot=0,ans1,ans2,dis[N],q[N],tou,wei,pre[N];
bool p[N];
void add(int u,int w,int z)
{
tot++;
way[tot].x=u;way[tot].y=w;way[tot].v=z;way[tot].nxt=st[u];st[u]=tot;
tot++;
way[tot].x=w;way[tot].y=u;way[tot].v=z;way[tot].nxt=st[w];st[w]=tot;
}
int spfa(int s,int t)
{
tou=wei=0;
q[++wei]=s;
memset(pre,0,sizeof(pre));
memset(dis,0x33,sizeof(dis));
dis[s]=0;
memset(p,1,sizeof(p));
p[s]=0;
do
{
int r=q[++tou];
for (int i=st[r];i;i=way[i].nxt)
{
if (dis[way[i].y]>dis[r]+way[i].v)
{
dis[way[i].y]=dis[r]+way[i].v;
pre[way[i].y]=i;
if (p[way[i].y])
{
q[++wei]=way[i].y;
p[way[i].y]=0;
}
}
}
p[r]=1;
}
while (tou<wei);
return dis[t];
}
int spfa2(int s,int t)
{
tou=wei=0;
q[++wei]=s;
memset(dis,0x33,sizeof(dis));
dis[s]=0;
memset(p,1,sizeof(p));
p[s]=0;
do
{
int r=q[++tou];
for (int i=st[r];i;i=way[i].nxt)
{
if (dis[way[i].y]>dis[r]+way[i].v)
{
dis[way[i].y]=dis[r]+way[i].v;
if (p[way[i].y])
{
q[++wei]=way[i].y;
p[way[i].y]=0;
}
}
}
p[r]=1;
}
while (tou<wei);
return dis[t];
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
for (int i=1;i<=m;i++)
{
int u,w,z;
scanf("%d%d%d",&u,&w,&z);
add(u,w,z);
}
ans1=spfa(s,t);
if (ans1==INF) {
printf("He lose his love
");
return 0;
}
ans2=INF;
for (int i=t;i!=s;i=way[pre[i]].x) //记录最短路
{
int u=way[pre[i]].v;
way[pre[i]].v=INF;
ans2=min(ans2,spfa2(s,t));
way[pre[i]].v=u; //别忘了恢复值
}
if (ans2==INF) printf("He will be cursed
");
else printf("%d
",ans2);
return 0;
}