bzoj 1880: [Sdoi2009]Elaxia的路线【spfa+拓扑排序】

2021-06-30 20:05

阅读：680

标签：stream string tor 排序 set names amp code min

有趣啊
先spfa分别求出以s1，t1，s2，t2为起点的最短路，然后把在s1-->t1或者s2-->t2最短路上的边重新建有向图，跑拓扑最长路即可

#include
#include
#include
#include
#include
using namespace std;
const int N=1505,inf=1e9;
int n,m,x1,x2,y1,y2,d[N],dis[N],h[N],cnt,s1[N],s2[N],t1[N],t2[N];
bool v[N];
struct qwe
{
    int ne,no,to,va;
}e[1000005];
struct bian
{
    int u,v,w;
    bian(int U=0,int V=0,int W=0)
    {
        u=U,v=V,w=W;
    }
};
vectorve;
void add(int u,int v,int w)
{
    cnt++;
    e[cnt].ne=h[u];
    e[cnt].no=u;
    e[cnt].to=v;
    e[cnt].va=w;
    h[u]=cnt;
}
void spfa(int s,int dis[])
{
    queueq;
    for(int i=1;idis[u]+e[i].va)
            {
                dis[e[i].to]=dis[u]+e[i].va;
                if(!v[e[i].to])
                {
                    v[e[i].to]=1;
                    q.push(e[i].to);
                }
            }
    }
}
int main()
{
    scanf("%d%d%d%d%d%d",&n,&m,&x1,&y1,&x2,&y2);
    for(int i=1,x,y,v;iq;
    for(int i=1;i

bzoj 1880: [Sdoi2009]Elaxia的路线【spfa+拓扑排序】

标签：stream string tor 排序 set names amp code min

原文地址：https://www.cnblogs.com/lokiii/p/9639662.html

上一篇：POJ1591 M*A*S*H (JAVA)

下一篇：性能测试工具LoadRunner13-LR之Virtual User Generator 创建java脚本

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：bzoj 1880: [Sdoi2009]Elaxia的路线【spfa+拓扑排序】
文章链接：http://soscw.com/index.php/essay/99994.html

亲，登录后才可以留言！

bzoj 1880: [Sdoi2009]Elaxia的路线【spfa+拓扑排序】

评论

热门文章

推荐文章

最新文章

置顶文章