[USACO06NOV]路障Roadblocks

发表于 | 分类于
字数统计: 366 | 阅读时长 ≈ 2

和次小生成树相似的套路
记f 为S 到所有点的最短路，g 为T 到所有点的最短路
枚举所有边

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<cstdio>
#include<queue>
using namespace std;
const int N=5050,INF=1<<30;
int n,m,d[2][N],inq[N],mins=INF,ans=INF;
vector<int> e[N],g[N];
queue<int> Q;
inline int read()
{
    register int x=0,t=1;
    register char ch=getchar();
    while (ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
    if (ch=='-') t=-1,ch=getchar();
    while (ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*t;
}
void add(int u,int v,int val)
{
    e[u].push_back(v);
    g[u].push_back(val);
}
void SPFA(int s,int k)
{
    for(int i=1;i<=n;i++) d[k][i]=INF;
    d[k][s]=0,inq[s]=1,Q.push(s);
    while (!Q.empty())
    {
        int x=Q.front();
        inq[x]=0,Q.pop();
        for(int i=0;i<e[x].size();i++)
        {
            int to=e[x][i];
            if (d[k][x]+g[x][i]<d[k][to])
            {
                d[k][to]=d[k][x]+g[x][i];
                if (!inq[to]) inq[to]=1,Q.push(to);
            }
        }
    }
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        int val=read();
        add(u,v,val);
        add(v,u,val);
    }
    SPFA(1,0),SPFA(n,1);
    mins=d[0][n];
    for(int i=1;i<=n;i++)
        for(int j=0;j<e[i].size();j++)
        {
            int u=i,v=e[i][j];
            if (d[0][u]+g[i][j]+d[1][v]>mins)
                ans=min(ans,d[0][u]+g[i][j]+d[1][v]);
        }
    printf("%d\n",ans);
    return 0;
}