题目链接:Codeforces 449B Jzzhu and Cities
题目大意:Jzzhu是一个国家的总统,这个国家有N座城市,以1为首都,已经存在了M条公路,给定M条路。并且还有K条铁轨,铁轨均有首都出发,连接si,距离为yi。现在Jzzhu想要节省经费,拆除一些铁轨,问说最多能拆除多少个铁轨,要求每座城市与首都的最短距离不变。
解题思路:最短路,多加一个标记数组,每个si标记1,如果这些点的最短距离被更新,则将对应si的标记清为0,最后统计一下剩余的标记,即为不能拆除的铁轨。
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int N, M, K, p[maxn], vis[maxn];
ll d[maxn];
vector<pii> g[maxn];
void init () {
scanf("%d%d%d", &N, &M, &K);
int u, v, x;
for (int i = 0; i < M; i++) {
scanf("%d%d%d", &u, &v, &x);
g[u].push_back(make_pair(v, x));
g[v].push_back(make_pair(u, x));
}
}
int solve () {
for (int i = 0; i <= N; i++)
d[i] = INF;
d[1] = 0;
memset(p, 0, sizeof(p));
queue<int> que;
vis[1] = 1;
que.push(1);
for (int i = 1; i <= K; i++) {
int u, x;
scanf("%d%d", &u, &x);
if (d[u] > x) {
d[u] = x; p[u] = 1;
if (vis[u] == 0) {
vis[u] = 1;
que.push(u);
}
}
}
while (!que.empty()) {
int u = que.front();
que.pop();
vis[u] = 0;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i].first, x = g[u][i].second;
if (d[v] >= d[u] + x && p[v])
p[v] = 0;
if (d[v] > d[u] + x) {
d[v] = d[u] + x;
if (vis[v] == 0) {
vis[v] = 1;
que.push(v);
}
}
}
}
for (int i = 1; i <= N; i++)
K -= p[i];
return K;
}
int main () {
init();
printf("%d\n", solve());
return 0;
}
分享到:
相关推荐
jzzhu and cities problem realisation
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
Codeforces - 1107B. Digital root & 1107C. Brutality(规律 & 贪心)Codeforces - 1107B.
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces 185A - Plant 全测试点49个
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
Codeforces global round 10 codes
Codeforces round 678 division 2 codes
Some of the Codeforces problems codes
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
codeforces每日一题。 题意: 给出一个数组,让你挑选出能组成任意pair差值为2的幂的序列,并且使这个序列长度尽可能大。 思路: 针对于挑选出来的序列,任意pair对的差值为2的幂数。 假设有多个pair对,设dis(a,b)=2...
Codeforces round 678 D2_Codeforces_源码
一个Codeforces、牛客竞赛、AtCoder平台的编程竞赛查询插件,ACMer必备.zip
打codeforces的神器
codeforces-js Codeforces JS
接受串子-接受字符串相等-接受Codeforces回合#684(Div.2) 2/6 1440A-购买琴弦-接受1440B -中位数的总和-已接受1440C1-二进制表(简易版)-已接受1440C2-二进制表(硬版)-已接受 Codeforces回合#683(分区2) 1/...