Jzzhu and Cities

时间:2022-05-04 03:16:01

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的更多相关文章

  1. CF449B Jzzhu and Cities (最短路)

    CF449B CF450D http://codeforces.com/contest/450/problem/D http://codeforces.com/contest/449/problem/ ...

  2. Codeforces Round &num;257 &lpar;Div&period; 2&rpar; D题:Jzzhu and Cities 删特殊边的最短路

    D. Jzzhu and Cities time limit per test 2 seconds memory limit per test 256 megabytes input standard ...

  3. Codeforces 449 B&period; Jzzhu and Cities

    堆优化dijkstra,假设哪条铁路能够被更新,就把相应铁路删除. B. Jzzhu and Cities time limit per test 2 seconds memory limit per ...

  4. Codeforces C&period; Jzzhu and Cities(dijkstra最短路)

    题目描述: Jzzhu and Cities time limit per test 2 seconds memory limit per test 256 megabytes input stand ...

  5. CF449B Jzzhu and Cities 迪杰斯特拉最短路算法

    CF449B Jzzhu and Cities 其实这一道题并不是很难,只是一个最短路而已,请继续看我的题解吧~(^▽^) AC代码: #include<bits/stdc++.h> #d ...

  6. Codeforces 450D:Jzzhu and Cities(最短路,dijkstra)

    D. Jzzhu and Cities time limit per test: 2 seconds memory limit per test: 256 megabytes input: stand ...

  7. D&period; Jzzhu and Cities

    Jzzhu is the president of country A. There are n cities numbered from 1 to n in his country. City 1  ...

  8. codeforces 449B Jzzhu and Cities &lpar;Dij&plus;堆优化&rpar;

    输入一个无向图<V,E>    V<=1e5, E<=3e5 现在另外给k条边(u=1,v=s[k],w=y[k]) 问在不影响从结点1出发到所有结点的最短路的前提下,最多可以 ...

  9. Codeforces Round &num;257&lpar;Div&period;2&rpar; D Jzzhu and Cities --SPFA

    题意:n个城市,中间有m条道路(双向),再给出k条铁路,铁路直接从点1到点v,现在要拆掉一些铁路,在保证不影响每个点的最短距离(距离1)不变的情况下,问最多能删除多少条铁路 分析:先求一次最短路,铁路 ...

  10. Codeforces 450D Jzzhu and Cities &lbrack;heap优化dij&rsqb;

    #include<bits/stdc++.h> #define MAXN 100050 #define MAXM 900000 using namespace std; struct st ...

随机推荐

  1. 把一个SVN项目的目录结构 导入到另外一个空白的SVN项目里

    1 选好源目录,选中“check out” 2 选中想要的目录结构 3 选择具体的目录 4 确定,最后开始更新,成功!

  2. OpenRisc-67-OR的汇编

    引言 之前我们写过OR的裸机程序,写过基于OR的linux设备驱动程序,也反汇编过OR的机器码. 本小节,我们将通过一个简单的实验,对OR的汇编(指令集)做一个简单的梳理和測试. 1,基本思想 要想了 ...

  3. ASP&period;NET 常用内置对象详解-----Response

    利用提供的内置对象,可以实现页面之间的数据传递及实现一些特定的功能,如:缓冲输出,页面重定向等等. Response :响应,反应 Request:请求 Server:服务器 Application: ...

  4. cp 覆盖 &bsol;cp a test&bsol;a

    使用cp命令覆盖文件总是提示要输入yes或no,一个两个就算了,大量的文件复制就不行了,即使加上-f参数也无法强行覆盖.苦思冥想不得解,终于在查阅了众多资料后让我找到了解决方法,这里写出来,让有同样困 ...

  5. Lua学习&lpar;5&rpar;——迭代器与泛型for

    1. 迭代器 2. 泛型for语义 所谓迭代器就是一种可以遍历一种集合中所有元素的机制.在lua中,迭代器通常表示为函数,每调用依次函数就返回集合中的下一个元素.泛型for 内部保存了迭代器函数 实际 ...

  6. 51nod&lowbar;1298&colon;圆与三角形(计算几何)

    题目链接 判断圆和三角形是否相交   可以转化为   判断三条线段是否和圆相交 #include<iostream> #include<cstdio> #include< ...

  7. 记账本微信小程序开发四

    学习添加组件 集成日期组件 添加组件 需要在main.js文件中,声明一个data值date与wxml中的{{date}}绑定关联,然后在onLoad中初始化字符串格式的日期值, 处理日期组件点击确认 ...

  8. 『翻译』Android USB Host

    USB Host When your Android-powered device is in USB host mode, it acts as the USB host, powers the b ...

  9. 使用axios实现上传图片进度条

    在最近做的项目中,一个手机页面最多要上传几十张图片,虽然对照片做了压缩处理,不过最后还是很大,如果网卡的话,上传的时间很差,如果一直在loading的话,用户都不知道什自己上传了多少,为了更直观的展现 ...

  10. sql 2012之后分页查询速度问题

    一.SQL Server 2012使用OFFSET/FETCH NEXT分页,比SQL Server 2005/2008中的RowNumber()有显著改进.今天特地作了简单测试,现将过程分享如下: ...