Bakser's Blog

我是逗比。

bzoj1880 [Sdoi2009]Elaxia的路线

| Comments

noip夏令营讲的题.

当时myk神犇讲的是最短路网上dp。

没听懂

然后就用noip智商过了这道题。
先求出两条最短路之和,然后减去两头的部分再除二就可以了。
注意两头部分有两种情况。

bzoj1880
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N(1600);
const int M(N*N*2);
#define MIN(a,b) (((a)<(b))?(a):(b))
#define mp make_pair
typedef pair<int,int> pii;
struct hh
{
    int v,w,next;
}edges[M];
int point[N],n,m,s1,t1,s2,t2,dis[N],tot,d1,d2;
inline void addedge(int u,int v,int w)
{
    static int en(0);
    edges[++en].next=point[u];point[u]=en;
    edges[en].v=v;edges[en].w=w;
}
inline void dijkstra(int u)
{
    static priority_queue<pii,vector<pii>,greater<pii> > q;
    while(!q.empty())q.pop();
    memset(dis,0x7f,sizeof(dis));
    q.push(mp(dis[u]=0,u));
    while(!q.empty())
    {
        pii x(q.top());q.pop();
        int u(x.second);
        if(dis[u]!=x.first)continue;
        for(int i(point[u]);i;i=edges[i].next)
            if(dis[u]+edges[i].w<dis[edges[i].v])
            {
                dis[edges[i].v]=dis[u]+edges[i].w;
                q.push(mp(dis[edges[i].v],edges[i].v));
            }    
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    scanf("%d%d%d%d",&s1,&t1,&s2,&t2);
    for(int i(1),u,v,w;i<=m;i++)
    {
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
        addedge(v,u,w);
    }
    dijkstra(s1);
    tot=dis[t1];d1=dis[s2];d2=dis[t2];
    dijkstra(s2);
    tot+=dis[t2];d2+=dis[t1];
    dijkstra(t1);
    d1+=dis[t2];
    int ans(tot-MIN(d1,d2));
    if(ans<0)ans=0;
    printf("%d\n",ans>>1);
    return 0;
}

Comments

comments powered by Disqus