hdu 4707 bellman
最短路的优先队列做法：
#include<stdio.h>
#include<queue>
#include<string.h>
#define N 100010
#define inf 0x3fffffff
using namespace std;
int first[N],next[N],u[N],v[N],w[N],d[N];
int main()
{
int t,i,e,cnt,dis,n;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&dis);
for(i=0;i<n;i++)
first[i]=-1;
for(i=0;i<n-1;i++)
{
scanf("%d%d",&u[i],&v[i]);
w[i]=1;
next[i]=first[u[i]];
first[u[i]]=i;
}
priority_queue<int ,vector<int>,greater<int> >q;
int done[N];
for(i=0;i<n;i++)
d[i]=(i==0?0:inf);
memset(done ,0,sizeof(done));
q.push(0);
while(!q.empty())
{
int u=q.top();
q.pop();
if(done[u]) continue;
done[u]=1;
for(e=first[u];e!=-1;e=next[e])
if(d[v[e]]>d[u]+w[e])
{
d[v[e]]=d[u]+w[e];
q.push(v[e]);
}
}
cnt=0;
for(i=0;i<n;i++)
{
if(d[i]>dis)
cnt++;
}
printf("%d\n",cnt);
}
return 0;
}
bellman-ford()写法，普通的队列写法：
#include<stdio.h>
#include<queue>
#include<string.h>
#define N 100010
#define inf 0x3fffffff
using namespace std;
int first[N],next[N],u[N],v[N],w[N],d[N];
int main()
{
int t,i,e,cnt,dis,n;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&dis);
for(i=0;i<n;i++)
first[i]=-1;
for(i=0;i<n-1;i++)
{
scanf("%d%d",&u[i],&v[i]);
w[i]=1;
next[i]=first[u[i]];
first[u[i]]=i;
}
queue<int>q;
int done[N];
for(i=0;i<n;i++)
d[i]=(i==0?0:inf);
memset(done ,0,sizeof(done));
q.push(0);
while(!q.empty())
{
int u=q.front();
q.pop();
done[u]=0;
for(e=first[u];e!=-1;e=next[e])
if(d[v[e]]>d[u]+w[e])
{
d[v[e]]=d[u]+w[e];
if(!done[v[e]])
{
done[v[e]]=1;
q.push(v[e]);
}
}
}
cnt=0;
for(i=0;i<n;i++)
{
if(d[i]>dis)
cnt++;
}
printf("%d\n",cnt);
}
return 0;
}
最新文章
- 10月28日PHP基础知识测试题
- android 切换fragment的两种方式
- Emacs教程
- NetDMA
- centos查看硬件信息
- php 基础复习（2）GD库
- AnyCAD C++ SDK与OpenCASCADE互操作
- PHP实现的Mysql读写分离
- 如何删除Weblogic域
- Servlet基础之一：Servlet基本接口与类
- QT中嵌入SDL
- [每日一题] OCP1z0-047 :2013-08-29 NULL............................................................168
- 使用GNU/Linux播放电视节目
- drawable文件夹详解
- devexpress表格控件gridcontrol特殊应用（一）——实现禁用特定行（附源代码）
- 201521123081《java程序设计》 第7周学习总结
- IBM的websphere MQ的c#使用
- springboot 拦截器
- crontab命令详解
- ThinkPad T43续命记