ZOJ2923 Calculate Roads(SPFA上的dp)

时间:2022-09-20 16:43:18

算是学了图dp后的第一次应用吧。题目其实真的是非常不严谨,什么都没说,基本靠猜,而且严格来说数据应该会有爆int的,不过不管那么多啦,思路对了就好- -0

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#define ll long long
#define maxn 5000
#define maxm 1000000
#define inf 0x3f3f3f3f
using namespace std; vector<int> G[maxn+50]; struct Node
{
int v,k;
Node(){}
Node(int vi,int ki):v(vi),k(ki){}
}; int m,n,k;
int dis[maxn+50][55];
int num[maxn+50][55];
int vis[maxn+50][55];
int vtype[maxn]; int main()
{
while(cin>>m>>n>>k)
{
for(int i=0;i<=n;i++) G[i].clear();
int xi,yi;
for(int i=0;i<n;i++) {
scanf("%d%d",&xi,&yi);
vtype[xi]=yi;
}
for(int i=0;i<m;i++){
scanf("%d%d",&xi,&yi);
G[xi].push_back(yi);
G[yi].push_back(xi);
}
memset(dis,0x3f,sizeof(dis));
memset(num,0,sizeof(num));
queue<Node> que;
if(vtype[1]==0){
dis[1][0]=0;
num[1][0]=1;
que.push(Node(1,0));
}
else{
dis[1][1]=0;
num[1][1]=1;
que.push(Node(1,1));
}
while(!que.empty()){
Node xx=que.front();que.pop();
vis[xx.v][xx.k]=0;
int u=xx.v; int kk=xx.k;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(vtype[v]==0){
if(vis[v][kk]){
if(dis[u][kk]+1<dis[v][kk]){
dis[v][kk]=dis[u][kk]+1;
num[v][kk]=num[u][kk];
}
else if(dis[u][kk]+1==dis[v][kk]){
num[v][kk]+=num[u][kk];
}
}
else{
if(dis[u][kk]+1<dis[v][kk]){
dis[v][kk]=dis[u][kk]+1;
num[v][kk]=num[u][kk];
que.push(Node(v,kk));
vis[v][kk]=1;
}
else if(dis[u][kk]+1==dis[v][kk]){
num[v][kk]+=num[u][kk];
que.push(Node(v,kk));
vis[v][kk]=1;
}
}
}
else{
if(kk==k) continue;
if(vis[v][kk+1]){
if(dis[u][kk]+1<dis[v][kk+1]){
dis[v][kk+1]=dis[u][kk]+1;
num[v][kk+1]=num[u][kk];
}
else if(dis[u][kk]+1==dis[v][kk+1]){
num[v][kk+1]+=num[u][kk];
}
}
else{
if(dis[u][kk]+1<dis[v][kk+1]){
dis[v][kk+1]=dis[u][kk]+1;
num[v][kk+1]=num[u][kk];
que.push(Node(v,kk+1));
vis[v][kk+1]=1;
}
else if(dis[u][kk]+1==dis[v][kk+1]){
num[v][kk+1]+=num[u][kk];
que.push(Node(v,kk+1));
vis[v][kk+1]=1;
}
}
}
}
}
int mdis=inf;
for(int i=0;i<=k;i++){
mdis=min(mdis,dis[n][i]);
}
if(mdis==inf) {
puts("Impossible!");continue;
}
int ans=0;
for(int i=0;i<=k;i++){
if(dis[n][i]==mdis) ans+=num[n][i];
}
cout<<ans<<endl;
}
return 0;
}

ZOJ2923 Calculate Roads(SPFA上的dp)的更多相关文章

  1. ZOJ1232 Adventure of Super Mario spfa上的dp

    很早之前听说有一种dp是在图上的dp,然后是在跑SPFA的时候进行dp,所以特地找了一题关于在SPFA的时候dp的. 题意:1~a是村庄 a+1~a+b是城堡,存在m条无向边.求由a+b->1的 ...

  2. HDU3247 Resource Archiver &lpar;AC自动机&plus;spfa&plus;状压DP&rpar;

    Great! Your new software is almost finished! The only thing left to do is archiving all your n resou ...

  3. bzoj3380&colon; &lbrack;Usaco2004 Open&rsqb;Cave Cows 1 洞穴里的牛之一&lpar;spfa&plus;状压DP&rpar;

    数据最多14个有宝藏的地方,所以可以想到用状压dp 可以先预处理出每个i到j的路径中最小权值的最大值dis[i][j] 本来想用Floyd写,无奈太弱调不出来..后来改用spfa 然后进行dp,这基本 ...

  4. UVA - 10131Is Bigger Smarter&quest;(DAG上的DP)

    题目:UVA - 10131Is Bigger Smarter? (DAG) 题目大意:给出一群大象的体重和IQ.要求挑选最多的大象,组成一个序列.严格的体重递增,IQ递减的序列.输出最多的大象数目和 ...

  5. BZOJ 3998 TJOI2015 弦论 后缀自动机&plus;DAG上的dp

    题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3998 题意概述:对于一个给定长度为N的字符串,求它的第K小子串是什么,T为0则表示不同位置 ...

  6. 区间和序列上的dp

    区间上的dp状态设计最基本的形式: \(F[i]\)表示以i结尾的最优值或方案数. \(F[i][k]\)表示以i结尾附加信息为k的最优值或方案数. 当然可以有多维附加信息. 转移的话往往是枚举上一个 ...

  7. &lpar;板子&rpar;缩点 &plus; DAG上的DP(深搜)luogu P3387

    板子传送门 根据题目意思,我们只需要找出一条点权最大的路径就行了,不限制点的个数.那么考虑对于一个环上的点被选择了,一整条环是不是应该都被选择,这一定很优,能选干嘛不选.很关键的是题目还允许我们重复经 ...

  8. Travelling&lpar;spfa&plus;状态压缩dp&rpar;

    题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=3001 Travelling Time Limit: 6000/3000 MS (Java/Others ...

  9. 【学习笔记】有向无环图上的DP

    手动博客搬家: 本文发表于20180716 10:49:04, 原地址https://blog.csdn.net/suncongbo/article/details/81061378 首先,感谢以下几 ...

随机推荐

  1. jvm的代码缓存耗尽导致性能下降

    在没遇到这个问题之前,我对JVM的解释模式与编译模式的代码性能相差有多大,是没有感觉的,只是觉得编译模式会比解释模式性能好那么一点点吧. 但是经历过这次以后,让我对JVM的即时编译产生了兴趣.先来看看 ...

  2. ant批量执行Jmeter脚本

    JDK,Jmeter默认已经装了 ANT下载:http://ant.apache.org/bindownload.cgi ant环境变量需要配置 ant_home,你解压之后的地址 然后PATH环境变 ...

  3. RS-232-C串口通讯协议解析(硬件接口协议)

    http://www.dz3w.com/info/interface/0075524.html http://wenku.baidu.com/view/02cc247c27284b73f24250e3 ...

  4. windows平台下php版本问题–VC6&sol;VC9和TS&sol;NTS

    php下载页面中提供了4个下载版本,是vc6/vc9 与 TS/NTS的组合 VC6:legacy Visual Studio 6 compiler,就是使用这个编译器编译的.        VC9: ...

  5. Windows Mobile 常用键值VK对应表

    #define VK_TSOFT2              VK_F2  // Softkey 2  #define VK_TTALK                VK_F3  // Talk  ...

  6. 【BZOJ1305】跳舞(网络流)

    [BZOJ1305]跳舞(网络流) 题面 Description 一次舞会有n个男孩和n个女孩.每首曲子开始时,所有男孩和女孩恰好配成n对跳交谊舞.每个男孩都不会和同一个女孩跳两首(或更多)舞曲.有一 ...

  7. 【细小碎的oi小知识点总结贴】不定时更新(显然也没人看qwq)

    1.memcpy: 从a数组中复制k个元素到b数组: memcpy(b,a,sizeof(int)*k); #include<cstring> #include<iostream&g ...

  8. java使用httpclient封装post请求和get的请求

    在我们程序员生涯中,经常要复用代码,所以我们应该养成时常整理代码的好习惯,以下是我之前封装的httpclient的post和get请求所用的代码: package com.marco.common; ...

  9. LeetCode(41):缺失的第一个正数

    Hard! 题目描述: 给定一个未排序的整数数组,找出其中没有出现的最小的正整数. 示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3: 输 ...

  10. vue项目动态控制数据变动时箭头样式

    html代码 <div class="top_precent"> <span :class="{arrow:numPrecent<0}" ...