hdu3986 spfa + 枚举最短路上的边
题意:
删除一条边后,求最短路中最长的那个(敌人搞破坏).
思路:
如果你是敌人你肯定删除最短路上的边,删除别的边最短路的值是不会变的,所以直接枚举最短路上的边去删除,取得最大的就行了...
#include<stdio.h>
#include<string.h>
#include<queue>
#define N_node 1005
#define N_eage 110000
#define inf 1000000000
using namespace std;
typedef struct
{
int from ,to ,next ,cost;
}STAR;
STAR E[N_eage];
int list[N_node] ,tot;
int mer[N_eage] ,s_x[N_node];
void add(int a ,int b ,int c)
{
E[++tot].from = a;
E[tot].to = b;
E[tot].cost = c;
E[tot].next = list[a];
list[a] = tot;
}
void spfa(int s ,int n ,int key)
{
int mark_q[N_node] = {0};
mark_q[s] = 1;
for(int i = 0 ;i <= n ;i ++)
s_x[i] = inf;
s_x[s] = 0;
queue<int>q;
q.push(s);
if(key == -1)
memset(mer ,255 ,sizeof(mer));
while(!q.empty())
{
int xin ,tou;
tou = q.front();
q.pop();
mark_q[tou] = 0;
for(int k = list[tou] ;k ;k = E[k].next)
{
if(k == key) continue;
xin = E[k].to;
if(s_x[xin] > s_x[tou] + E[k].cost)
{
s_x[xin] = s_x[tou] + E[k].cost;
if(key == -1) mer[xin] = k;
if(!mark_q[xin])
{
mark_q[xin] = 1;
q.push(xin);
}
}
}
}
return ;
}
int main ()
{
int t ,i ,n ,m ,a ,b ,c;
scanf("%d" ,&t);
while(t--)
{
scanf("%d%d" ,&n ,&m);
memset(list ,0 ,sizeof(list));
tot = 1;
while(m--)
{
scanf("%d %d %d" ,&a ,&b ,&c);
add(a ,b ,c);
add(b ,a ,c);
}
int ans = -1;
spfa(1 ,n ,-1);
int kg = 0;
for(i = mer[n] ;i + 1 ;i = mer[E[i].from])
{
spfa(1 ,n ,i);
if(s_x[n] == inf)
{
kg = 1;
break; /////*********如果有一个边删除后不连通了,那么敌人肯定毁灭着一条.
}
if(ans < s_x[n] )
ans = s_x[n];
}
if(kg) ans = -1;
printf("%d\n" ,ans);
}
return 0;
}
最新文章
- ArrayList、Vector、HashMap、HashSet的默认初始容量、加载因子、扩容增量
- SQL Server 2012附加数据库时,错误提示如下:尝试打开或创建物理时,CREATE FILE 遇到操作系统错误 5(拒绝访问。)
- sqlserver 查看正在执行sql
- 导出Excel offer2007以上
- 10个免费的PHP编辑器/开发工具
- Timer 实现2秒4秒连环炸
- Android 二维码扫描与生成
- J2EE开发常用开源框架技术(转)
- vmware中ubuntu更新内核后无法进入桌面,鼠标“漂移”滑动
- OpenCV-Python教程(10、直方图均衡化)
- python正则匹配示例
- menuStrip1动态添加菜单及快捷键
- js倒计时、计时开始
- Linux 的文件软链接如何删除
- 57. 激活office时出下以下问题的解决方案
- RESTful介绍和使用教程
- jQuery-对标签元素 文本操作-属性操作-文档的操作
- volatile关键字的介绍和使用
- Orchard Core 使用工作流处理审批和创建内容项
- 使用nodejs创建加入用户验证的websocket服务