关键词：
链接： 2018-2019 ICPC Southwestern European Regional Programming Contest (SWERC 2018)
题意：
一个无向图，图上有三个关键点A，B，C，统计图上点u的个数，满足没有其他点v到A,B,C的最短距离都比u到A,B,C的最短距离小(uA>=vA && uB>=vB && uC>=vC &&(uA>vA || uB>vB || uC>vC) )
解法:
先跑3次dijkstra，求出所有点到A,B,C的距离，然后按照到A的距离从小到大排序。从前往后遍历，用线段树查询此时<=b的最小C值，如果比当前C大，该点就加入答案中。
考虑到距离相等的情况，先用map去重，并记录重复点的个数，每次加入答案的就是点的个数。
因为距离最大有5e7，需要把距离离散化
代码：
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int maxn = 1e5 + 5;
const int maxm = 2e5 + 5;
struct node
int id, cost;
node(int a = 0, int b = 0) :id(a), cost(b)
bool operator<(const node &b)const
return cost > b.cost;//将小的放上面
;
struct edge
int v, cost;
edge(int a = 0, int b = 0) :v(a), cost(b)
;
vector<edge>E[maxm];
int dis[3][maxn];
bool vis[maxn];
void dijkstra(int n, int start,int *lowcost)
fill(vis + 1, vis + 1 + n, 0);
fill(lowcost + 1, lowcost + 1 + n, INF);
priority_queue<node>q;
lowcost[start] = 0;
q.push(node(start, 0));
while (!q.empty())
int u = q.top().id;
q.pop();
if (vis[u])continue;
vis[u] = 1;
for (int i = 0; i < E[u].size(); i++)
int v = E[u][i].v;
int cost = E[u][i].cost;
if (!vis[v] && lowcost[v] > lowcost[u] + cost)
lowcost[v] = lowcost[u] + cost;
q.push(node(v, lowcost[v]));
void addedge(int u, int v, int w)
E[u].push_back(edge(v, w));
struct Point
int a,b,c;
operator<(const Point &B)const
if(a!=B.a)
return a<B.a;
else if(b!=B.b)
return b<B.b;
else
return c<B.c;
p[maxn];
int lisan[maxn*3];
int lisancnt=0;
//------线段树-------------
const int M=1<<19;//从1开始，不能修改0和M
int T[M+M];
void modify(int n,int v)
for(T[n+=M]=v,n>>=1;n;n>>=1)
T[n]=min(T[n+n],T[n+n+1]);
int query(int l,int r)
int rmin=INF,lmin=INF;
for(l+=M-1,r+=M+1;l^r^1;l>>=1,r>>=1)
if(~l&1) lmin=min(lmin,T[l^1]);
if(r&1) rmin=min(rmin,T[r^1]);
return min(lmin,rmin);
//------------------------
int main()
int n, m, u, v, w;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
scanf("%d%d%d", &u, &v, &w);
u++; v++;
addedge(u, v, w);
addedge(v, u, w);
dijkstra(n, 1, dis[0]);
dijkstra(n, 2, dis[1]);
dijkstra(n, 3, dis[2]);
for (int i = 1; i <= n; i++)
p[i]=dis[0][i],dis[1][i],dis[2][i];
map<Point,int>MA;
for(int i=1;i<=n;i++)
lisan[++lisancnt]=p[i].a;
lisan[++lisancnt]=p[i].b;
lisan[++lisancnt]=p[i].c;
sort(lisan+1,lisan+1+lisancnt);
int lisansize=unique(lisan+1,lisan+1+lisancnt)-(lisan + 1);
for(int i=1;i<=n;i++)
p[i].a=lower_bound(lisan+1,lisan+1+lisansize,p[i].a)-lisan;
p[i].b=lower_bound(lisan+1,lisan+1+lisansize,p[i].b)-lisan;
p[i].c=lower_bound(lisan+1,lisan+1+lisansize,p[i].c)-lisan;
MA[p[i]]++;
int cnt=0;
for(auto poi:MA)
p[++cnt]=poi.first;
sort(p+1,p+1+cnt);
int ans=0;
fill(T,T+M+M-1,INF);
for(int i=1;i<=cnt;i++)
if(query(1,p[i].b)>p[i].c)//该点是有用的
ans+=MA[p[i]];
modify(p[i].b,p[i].c);
printf("%d
",ans);
/*
5 4
0 3 1
1 3 1
2 3 1
4 3 1
5 6
0 3 1
1 3 1
2 3 1
4 3 1
0 1 1
0 2 1
*/
markdowngit代码片段(代码片段)
csharp代码片段(代码片段)
javascript代码片段(代码片段)
textvisualbasic代码片段(代码片段)
sqloracle代码片段(代码片段)
swift代码片段(代码片段)
java代码片段【安卓】(代码片段)
shbash的代码片段(代码片段)
markdownphpexcelnotes和代码片段(代码片段)
javaandroid的代码片段(代码片段)
javascriptjs-常用代码片段(代码片段)
常用代码片段(代码片段)
单例模式privatestaticHttpUtilinstance;publicstaticsynchronizedHttpUtilgetInstance()if(instance==null)instance=newHttpUtil();returninstance; 查看详情
常用代码片段(代码片段)
单例模式privatestaticHttpUtilinstance;publicstaticsynchronizedHttpUtilgetInstance()if(instance==null)instance=newHttpUtil();returninstance; 查看详情
text代码片段很有用(代码片段)
vbscript我的代码片段(代码片段)
java代码片段【java】(代码片段)
rr有用的代码片段(代码片段)
常见的代码片段(代码片段)
$(id).select2(placeholder:"--请选择--",allowClear:true,data:list); 查看详情