ACdream 1415 Important Roads
Important Roads
Problem Description
The city where Georgie lives has n junctions some of which are connected by bidirectional roads.
Every day Georgie drives from his home to work and back. But the roads in the city where Georgie lives are very bad, so they are very often closed for repair. Georgie noticed that when some roads are closed he still can get from home to work in the same time as if all roads were available.
But there are such roads that if they are closed for repair the time Georgie needs to get from home to work increases, and sometimes Georgie even cannot get to work by a car any more. Georgie calls such roads important.
Help Georgie to find all important roads in the city.
Input
The first line of the input file contains n and m — the number of junctions and roads in the city where Georgie lives, respectively (2 ≤ n ≤ 20 000, 1 ≤ m ≤ 100 000). Georgie lives at the junction 1 and works at the junction n.
The following m lines contain information about roads. Each road is specified by the junctions it connects and the time Georgie needs to drive along it. The time to drive along the road is positive and doesn’t exceed 100 000. There can be several roads between a pair of junctions, but no road connects a junction to itself. It is guaranteed that if all roads are available, Georgie can get from home to work.
Output
Sample Input
6 7
1 2 1
2 3 1
2 5 3
1 3 2
3 5 1
2 4 1
5 6 2
Sample Output
2
5 7
Source
Manager
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <set>
#include <stack>
#define LL long long
#define pli pair<long long,int>
#define INF 0x3f3f3f3f3f3fLL
using namespace std;
const int maxn = ;
struct arc{
int to,next;
LL w;
arc(int x = ,LL y = ,int z = -){
to = x;
w = y;
next = z;
}
};
struct edge{
int to,id,next;
edge(int x = ,int y = ,int z = -){
to = x;
id = y;
next = z;
}
};
arc e[maxn*];
edge g[maxn*];
int head[maxn],first[maxn],ans[maxn],tot2,num;
int n,m,tot,x[maxn*],y[maxn*],z[maxn*];
int dfn[maxn],low[maxn],idx;
LL d[][maxn];
void add(int u,int v,LL w){
e[tot] = arc(v,w,head[u]);
head[u] = tot++;
e[tot] = arc(u,w,head[v]);
head[v] = tot++;
}
void add2(int u,int v,int id){
g[tot2] = edge(v,id,first[u]);
first[u] = tot2++;
g[tot2] = edge(u,id,first[v]);
first[v] = tot2++;
}
void dijkstra(int s,LL ds[maxn]){
priority_queue< pli,vector< pli >,greater< pli > >q;
bool done[maxn] = {false};
for(int i = ; i <= n; i++) ds[i] = INF;
ds[s] = ;
q.push(make_pair(ds[s],s));
while(!q.empty()){
int u = q.top().second;
q.pop();
if(done[u]) continue;
done[u] = true;
for(int i = head[u]; ~i; i = e[i].next){
if(ds[e[i].to] > ds[u] + e[i].w){
ds[e[i].to] = ds[u] + e[i].w;
q.push(make_pair(ds[e[i].to],e[i].to));
}
}
}
}
void tarjan(int u,int fa){
dfn[u] = low[u] = ++idx;
bool flag = true;
for(int i = first[u]; ~i; i = g[i].next){
if(g[i].to == fa && flag){
flag = false;
continue;
}
if(!dfn[g[i].to]){
tarjan(g[i].to,u);
low[u] = min(low[u],low[g[i].to]);
if(low[g[i].to] > dfn[u]) ans[num++] = g[i].id;
}else low[u] = min(low[u],dfn[g[i].to]);
}
}
int main(){
while(~scanf("%d %d",&n,&m)){
memset(head,-,sizeof(head));
memset(first,-,sizeof(first));
memset(dfn,,sizeof(dfn));
memset(low,,sizeof(low));
idx = num = tot2 = tot = ;
for(int i = ; i <= m; i++){
scanf("%d %d %d",x+i,y+i,z+i);
add(x[i],y[i],z[i]);
}
dijkstra(,d[]);
dijkstra(n,d[]);
LL tmp = d[][n];
for(int i = ; i <= m; i++){
int u = x[i];
int v = y[i];
if(d[][u] + z[i] + d[][v] == tmp || d[][v] + z[i] + d[][u] == tmp){
add2(u,v,i);
}
}
for(int i = ; i <= n; i++)
if(!dfn[i]) tarjan(i,-);
printf("%d\n",num);
if(num){
for(int i = ; i < num; i++)
printf("%d%c",ans[i],i + == num?'\n':' ');
}
}
return ;
}
最新文章
- 【Network】Neutron-Docker-K8S
- Oracle 免费的数据库--Database 快捷版 11g 安装使用与";SOD框架";对Oracle的CodeFirst支持
- iOS开发系列之 itms-services 协议
- Java中构造函数执行顺序的问题
- sync_binlog innodb_flush_log_at_trx_commit 浅析 传
- 源泉书签,助您管理海量收藏。www.yuanquanshuqian.com,今日更新:多标签功能已实现
- Lombok介绍及使用方法
- Git 的是使用入门
- Example003通过按钮创建窗口
- js 中 new fn与new fn()的区别
- WebCracker4.0和monster字典——路由器登陆密码破解工具
- python 内置函数之lambda-filter-reduce-apply-map
- .net简介(一)
- Expression 生成 Lambda
- php使用curl模拟登录带验证码的网站[开发篇]
- Apollo 1 融合 Spring 的三个入口
- Instruments模板介绍(更新中...)
- alpa开发阶段团队贡献分
- 服务端怎样暴露IBinder接口对象
- 使用libvirt管理KVM(一)
热门文章
- C++开发人脸性别识别教程(12)——加入性别识别功能
- &;quot;高可用方案工具包&;quot; high availability toolkit 1.1
- BZOJ 4517: [Sdoi2016]排列计数 错排+逆元
- XML基础+Java解析XML +几种解析方式的性能比较
- 关于jetty服务器默认首页和端口设置
- EOJ 1114 素数环
- JDBC数据库中表更新
- mysqls,为node.js而编写的sql语句生成插件 (crud for mysql).
- java三大版本解析
- 常用的CSS命名