CF #257 div2D:http://codeforces.com/contest/450/problem/D
题意:给你n个城市,m条无向有权边。另外还有k条边,每条边从起到到i。求可以删除这k条边中的多少条,使得每个点到1的最短距离不变。
题解:通过这一题明白了,对于一个问题要有分析思考的能力。首先分析一下,对于城市i,(1)如果没有从1到i的特殊边(即上述k条中的一条),我们不用考虑。(2)如果有,在这之前已经求出了每个点的最短路,如果这条边的边权大于等于最短路,则可以直接删除,一不会影响本身的最短路,二不会影响别的城市,因为别的城市可以通过当前已经求得的最短路进行松弛。(3)如果这个边权边权小于最短路,那么我们把最短路路径修改为这个距离,接下就要判断,能否通过其它的点来求得当前的最短路或者更短,很明显,如果能够求得到这个距离,说明可以通过其它点来得到这个最短路,那么这一条路径可以删除了,否则就是唯一的。对于这一来说,如果用链式前向星来存图的话,我的是T了,也许是哪里没有处理好,改成Vecotr就A了。这确实是不错的题目。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#define INF 10000000000000000LL
#define ll long long
using namespace std;
const int N=1e5+;
const int M=*1e5+;
int n,m,k,ans,u,v;
long long temp,dist1[N],dist2[N],dist3[N];
bool flag[N],visit[N];
struct Edge{
int v;
ll w;
Edge(int vi, ll wi) : v(vi), w(wi){}
Edge(){}
};
vector<Edge>G[N];
void SPFA1(int u){
for(int i=;i<=n;i++){
dist1[i]=INF;
visit[i]=;
}
queue<int>Q;
dist1[u]=;
visit[u]=;
Q.push(u);
while(!Q.empty()){
int v=Q.front();
Q.pop();
visit[v]=;
for (int i = ; i < G[v].size(); i++){
int d = G[v][i].v; ll w = G[v][i].w;
if(dist1[d]>dist1[v]+w){
dist1[d]=dist1[v]+w;
if(!visit[d]){
Q.push(d);
visit[d]=;
}
}
}
}
}
void SPFA2(int u){
for(int i=;i<=n;i++){
visit[i]=;
dist3[i]=INF;
}
queue<int>Q;
dist3[u]=;
visit[u]=;
Q.push(u);
for(int i=;i<=n;i++){
if(dist2[i]<dist1[i]){
Q.push(i);
visit[i]=;
dist3[i]=dist2[i];
}
}
while(!Q.empty()){
int v=Q.front();
Q.pop();
visit[v]=;
for (int i = ; i < G[v].size(); i++){
int d = G[v][i].v; ll w = G[v][i].w;
if(dist3[d]>dist3[v]+w){
dist3[d]=dist3[v]+w;
if(!visit[d]){
Q.push(d);
visit[d]=;
}
if(flag[d]){
ans++;
flag[d]=;
}
}
else if(dist3[d]==dist3[v]+w){
if(flag[d]){
ans++;
flag[d]=;
}
}
}
}
}
int main(){
while(~scanf("%d%d%d",&n,&m,&k)){
for (int i = ; i <= n; i++) G[i].clear();
for(int i=;i<=m;i++){
scanf("%d%d%I64d",&u,&v,&temp);
G[u].push_back(Edge(v,temp));
G[v].push_back(Edge(u,temp));
}
SPFA1();
ans=;memset(flag,,sizeof(flag));
for(int i=;i<=n;i++)
dist2[i]=dist1[i];
for(int i=;i<=k;i++){
scanf("%d%I64d",&v,&temp);
if(dist2[v]<=temp)ans++;
else{
dist2[v]=temp;
if(flag[v])ans++;
flag[v]=;
}
}
SPFA2();
printf("%d\n",ans);
}
}
Jzzhu and Cities的更多相关文章
-
CF449B Jzzhu and Cities (最短路)
CF449B CF450D http://codeforces.com/contest/450/problem/D http://codeforces.com/contest/449/problem/ ...
-
Codeforces Round #257 (Div. 2) D题:Jzzhu and Cities 删特殊边的最短路
D. Jzzhu and Cities time limit per test 2 seconds memory limit per test 256 megabytes input standard ...
-
Codeforces 449 B. Jzzhu and Cities
堆优化dijkstra,假设哪条铁路能够被更新,就把相应铁路删除. B. Jzzhu and Cities time limit per test 2 seconds memory limit per ...
-
Codeforces C. Jzzhu and Cities(dijkstra最短路)
题目描述: Jzzhu and Cities time limit per test 2 seconds memory limit per test 256 megabytes input stand ...
-
CF449B Jzzhu and Cities 迪杰斯特拉最短路算法
CF449B Jzzhu and Cities 其实这一道题并不是很难,只是一个最短路而已,请继续看我的题解吧~(^▽^) AC代码: #include<bits/stdc++.h> #d ...
-
Codeforces 450D:Jzzhu and Cities(最短路,dijkstra)
D. Jzzhu and Cities time limit per test: 2 seconds memory limit per test: 256 megabytes input: stand ...
-
D. Jzzhu and Cities
Jzzhu is the president of country A. There are n cities numbered from 1 to n in his country. City 1 ...
-
codeforces 449B Jzzhu and Cities (Dij+堆优化)
输入一个无向图<V,E> V<=1e5, E<=3e5 现在另外给k条边(u=1,v=s[k],w=y[k]) 问在不影响从结点1出发到所有结点的最短路的前提下,最多可以 ...
-
Codeforces Round #257(Div.2) D Jzzhu and Cities --SPFA
题意:n个城市,中间有m条道路(双向),再给出k条铁路,铁路直接从点1到点v,现在要拆掉一些铁路,在保证不影响每个点的最短距离(距离1)不变的情况下,问最多能删除多少条铁路 分析:先求一次最短路,铁路 ...
-
Codeforces 450D Jzzhu and Cities [heap优化dij]
#include<bits/stdc++.h> #define MAXN 100050 #define MAXM 900000 using namespace std; struct st ...
随机推荐
-
把一个SVN项目的目录结构 导入到另外一个空白的SVN项目里
1 选好源目录,选中“check out” 2 选中想要的目录结构 3 选择具体的目录 4 确定,最后开始更新,成功!
-
OpenRisc-67-OR的汇编
引言 之前我们写过OR的裸机程序,写过基于OR的linux设备驱动程序,也反汇编过OR的机器码. 本小节,我们将通过一个简单的实验,对OR的汇编(指令集)做一个简单的梳理和測试. 1,基本思想 要想了 ...
-
ASP.NET 常用内置对象详解-----Response
利用提供的内置对象,可以实现页面之间的数据传递及实现一些特定的功能,如:缓冲输出,页面重定向等等. Response :响应,反应 Request:请求 Server:服务器 Application: ...
-
cp 覆盖 \cp a test\a
使用cp命令覆盖文件总是提示要输入yes或no,一个两个就算了,大量的文件复制就不行了,即使加上-f参数也无法强行覆盖.苦思冥想不得解,终于在查阅了众多资料后让我找到了解决方法,这里写出来,让有同样困 ...
-
Lua学习(5)——迭代器与泛型for
1. 迭代器 2. 泛型for语义 所谓迭代器就是一种可以遍历一种集合中所有元素的机制.在lua中,迭代器通常表示为函数,每调用依次函数就返回集合中的下一个元素.泛型for 内部保存了迭代器函数 实际 ...
-
51nod_1298:圆与三角形(计算几何)
题目链接 判断圆和三角形是否相交 可以转化为 判断三条线段是否和圆相交 #include<iostream> #include<cstdio> #include< ...
-
记账本微信小程序开发四
学习添加组件 集成日期组件 添加组件 需要在main.js文件中,声明一个data值date与wxml中的{{date}}绑定关联,然后在onLoad中初始化字符串格式的日期值, 处理日期组件点击确认 ...
-
『翻译』Android USB Host
USB Host When your Android-powered device is in USB host mode, it acts as the USB host, powers the b ...
-
使用axios实现上传图片进度条
在最近做的项目中,一个手机页面最多要上传几十张图片,虽然对照片做了压缩处理,不过最后还是很大,如果网卡的话,上传的时间很差,如果一直在loading的话,用户都不知道什自己上传了多少,为了更直观的展现 ...
-
sql 2012之后分页查询速度问题
一.SQL Server 2012使用OFFSET/FETCH NEXT分页,比SQL Server 2005/2008中的RowNumber()有显著改进.今天特地作了简单测试,现将过程分享如下: ...