cogs 826. Feb11] GF打dota

 

★★☆   输入文件:dota.in   输出文件:dota.out   简单对比
时刻范围:1 s   内存限制:128 MB

众目睽睽,GF同学喜欢打dota,而且自得甚好。今天GF和Spartan同学进行了扳平摆战火。

而今GF拿到同一张地图,地图及共发n个地点,GF的勇猛处于1哀号点,Spartan的驻地位于n号点,

GF要趁早地摘比较短的途径给他的奋不顾身去虐掉Spartan的基地。但是Spartan早就料到了及时或多或少,

外起或会见开挂(BS~)使用同样种专门之魔法,一旦GF所动的途径的毕竟长度等最短路的究竟长度时,

GF的英雄就要跟这种魔法纠缠不休。这时GF就只能选择无最缺乏的途径。现在要您替GF进行设计。

于描述的讲和唤醒:
1.不论是往路,花费时间本为非负值。

2.对主题中非极缺乏路线的概念:不管采取其它迂回、改道方式,

假设GF所走之路子总长度不对等1暨n最短路的究竟长度时,就到底做一样漫漫未最缺少的路。

3.保证1~n有路可走。

输入:

率先行为n,m(表示一共有m长达路)
搭下去m行,每行3独整数a,b,c,表示编号为a,b的点间并在同修花费时间为c的凭为路。
联网下去一行来一个平头p,p=0表示Spartan没有开挂使用这种魔法,p=1则意味着以了。

输出:

所消费的卓绝缺少时间t,数据保证得得到达n。

样例输入1:
5 5
1 2 1
1 3 2
3 5 2
2 4 3
4 5 1
0

样例输入2:
5 5
1 2 1
1 3 2
3 5 2
2 4 3
4 5 1
1

样例输出1:
4
样例输出2:
5

对于50%的数据,1<=n,m<=5000
对于70%的数据,1<=n<=10000, 1<=m<=50000,p=0,
对于100%的数据,1<=n<=10000, 1<=m<=50000,p=1
任由为图,花费时间c>=0

各个测试点1s

来源:lydliyudong    Tyvj
February二月月赛第二集  第2道

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>

using namespace std;
const int N=100010;
const int INF=99999999; 

int now1=1,now2=1;
int dis[N],head1[N];
int sta,ed;
bool vis[N];
int ans[N];
int n,m,k,js;
struct fan{
    int u,v,w,nxt;
}F[N];
struct zheng{
    int u,v,w,nxt;
}Z[N];
struct node{
    int point,noww,will;
}now,topp,nxt;

inline int read()
{
    int x=0;int f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x*f;
}

inline void addzheng(int u,int v,int w)
{Z[now1].v=v;Z[now1].w=w;Z[now1].nxt=head1[u];head1[u]=now1++;}

bool operator < (node a,node b)
{return a.will>b.will;}

inline void spfa(int start)
{
    queue<int>q;
    for(int i=1;i<=n;i++)dis[i]=INF,vis[i]=0;
    dis[start]=0;vis[start]=1;
    q.push(start);
    while(!q.empty())
    {
        int ttop=q.front();q.pop();
        vis[ttop]=0;
        for(int i=head1[ttop];~i;i=Z[i].nxt)
            if(dis[Z[i].v]>dis[ttop]+Z[i].w)
                {dis[Z[i].v]=dis[ttop]+Z[i].w;if(!vis[Z[i].v])vis[Z[i].v]=1,q.push(Z[i].v);}
    }
}

inline void Astar(int start,int endd)
{
    if(dis[start]==INF)return ;
    now.point=start,now.noww=0;now.will=dis[start];
    priority_queue<node>q;
    q.push(now);
    while(!q.empty())
    {
        topp=q.top();
        q.pop();
        if(topp.point==endd){ans[++js]=topp.noww;if(js==2)return ;}
        for(int i=head1[topp.point];~i;i=Z[i].nxt)
            {nxt.point=Z[i].v;nxt.noww=topp.noww+Z[i].w;nxt.will=nxt.noww+dis[Z[i].v];q.push(nxt);}
    }
}

int main()
{
    freopen("dota.in","r",stdin);
    freopen("dota.out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=n;i++)head1[i]=-1;
    for(int i=1;i<=m;i++)
        {int u=read(),v=read(),w=read();addzheng(u,v,w);addzheng(v,u,w);}
    sta=1;ed=n;k=read();
    spfa(ed);
    Astar(sta,ed);
    if(!k)printf("%d\n",ans[1]);
    else printf("%d\n",ans[2]);
    return 0;
} 

  

 

1.模拟:

luogu p1563 玩具谜题   codevs顶差数列  cogs  求和问题 积木大赛   扫雷游戏

拼数  cover  被窃的项链  小A的糖果   P1583 魔法照片  如法炮制只会猜题意  1806. [NOIP2014]无线网路发射器选址  luogu P1307 数字反转  luogu P1422 小玉家的电费   luogu P1217 [USACO1.5]拨文质数 Prime
Palindromes  3D模型  luogu 金币

cogs 求和

2.最短路:

 (1):Dijkstra  luogu 大陆争霸  luogu1576极小花费

 (2):floyd     luogu 电车    牛大赛    最短路  期小学    67. [NOI1997] 最了不起乘车  176. [USACO Feb07] 奶牛聚会 cogs 找最佳通路 

  (3):spfa    向奥格瑞玛的征程    luogu 玛丽卡   不过缺乏路程计数(spfa+dfs)    医院设置   P1772 [ZJOI2006]物流运输(spfa+dp)  libreoj最短路  tyvj
丛林探险  P2296 寻找道路  cogs 2. 旅行计划

  (4):topsoart  cogs 牛跑步  森林大礼包 

(5):最小环:信传递  vijos 观光旅游 最小环fl
呆详看

(6):k短路:牛跑步
A*k短路算法   GF打dota

3.Dp

   luogu 乘积最老  过河(wd)  没有上级的舞会   贪得无厌的果农  不过特别正方形子矩(WD)

  luogu  找GF    luogu1659养猪  P2066 机器分配  P2196 挖地雷  

  luogu 组合数问题   luogu P2285
[HNOI2004]打鼹鼠  P1057
传球游戏

luogu  传纸条    luogu P1049 装箱问题

4.搜索:

 Bfs:luogu  位图  codevs 红与黑  codevs 游乐园的迷宫  codevs营救(wa)圆球细胞数量   luogu 填涂颜色 血色先锋队 01迷宫  引发那头牛  cogs世界树 (wa)
   马的遍历  传染病控制(wa)  codevs 1569 最佳绿草  单词方阵  油田

Dfs :  luogu 信息传送、   单词接上   选数   最好缺里程计数(spfa+dfs)  海战  luogu
1605 迷宫  [HAOI2016]食物链
记忆化  cogs5.
P服务点设置(dfs+flyod)

P1434 滑雪   

5.分治:

 luogu 砍树  codevs 电话网络(二分答案+spfa) 极接近神的人口_NOI导刊2010提高(02)逆序对  跳石头(二细分答案)  飞的函数  

6.并查集(图论) codevs 数轴染色  luogu星球大战 luogu 口袋的天  luogu 买礼物   兽径管理   151. [USACO Dec07] 建造路径 cogs 通信线路  亲戚

6.贪心: 排队接水  tyvj纪念品分组  tyvj羽毛  三角形牧场(贪心(WD)/dp)君打(高精+贪心)  

7.数学:删掉的界限  codevs 落单的一再  统计数字  笨小猴(素筛)

8.线段树:线段树1  线段树2  线段树3  线段树4

10.树状数组 :树状数组1  树状数组2

11.队列,堆,栈,链表:

  luogu 队排安排  小组队列  奶牛队列  luogu P3378 【模板】堆  P2564 [SCOI2009]生日礼物

12.莫队: luogu P2709 小B的询问  luogu cogs 421. HH的项链  cogs luogu 1901. [国家集训队2011]数颜色(待修改莫队)  1619. [HEOI2012]采花(TLE3)(树状数组)

13.RMQ : poj Balanced Lineup
RMQ

 

405461326387

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*
*
Website