专业制作网页公司价格,网站建设优化服务新闻,企业网站注册,设计网站官网入口J-xay loves Floyd
ANJHZ题解 abcdhhhh_题解 如果di,jwi,j\text d_{i,j}\text w_{i,j}di,jwi,j,那么按照题意中的算法仍然能得到正确的结果。此时记cani,j1\text{can}_{i,j}1cani,j1。 如果存在vvv#xff0c;使得①cani,v1\text{can}_{i,v}1cani,v1②canv,j1\text{…J-xay loves Floyd
ANJHZ题解 abcdhhhh_题解 如果di,jwi,j\text d_{i,j}\text w_{i,j}di,jwi,j,那么按照题意中的算法仍然能得到正确的结果。此时记cani,j1\text{can}_{i,j}1cani,j1。 如果存在vvv使得①cani,v1\text{can}_{i,v}1cani,v1②canv,j1\text{can}_{v,j}1canv,j1③vvv在iii到jjj的任意一条最短路上那么cani,j1\text{can}_{i,j}1cani,j1。
直接这么算can[i][j]can[i][j]can[i][j]复杂度太高我们注意到can[i][∗]can[i][*]can[i][∗]can[∗][j]can[*][j]can[∗][j]的运算本质上是集合求交可以利用bitset维护。 将can[i][∗]can[i][*]can[i][∗]记为bitsetN fr[i]can[∗][j]can[*][j]can[∗][j]记为bitsetNto[j]
同时枚举sss,则sss到jjj的所有最短路经过的点集potj\text{pot}_jpotj也可以通过bitset维护具体做法是每次枚举一个sss,就重新把顶点按照到sss的最短路长度排序从小到大计算potj\text{pot}_jpotj。如果ds,kwk,jds,j\text d_{s,k}\text w_{k,j}\text d_{s,j}ds,kwk,jds,j,则potj∣potk\text{pot}_j|\text{pot}_kpotj∣potk
时间复杂度O(nmlogmn2ww)O(nm\log m\frac{n^2w}{w})O(nmlogmwn2w)
Code
#includebits/stdc.h
using namespace std;
using lllong long;
template class Tint T rd()
{T res0;T fg1;char chgetchar();while(!isdigit(ch)) {if(ch-) fg-1;chgetchar();}while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res*fg;
}
const int N2005,M5005;
int h[N],e[M],ne[M],w[M],idx;
void add(int a,int b,int c){e[idx]b,ne[idx]h[a],w[idx]c,h[a]idx;}
int d[N][N];
int n,m;
bool st[N];
bitsetN pot[N],fr[N],to[N];void dij(int s,int d[])
{memset(st,0,sizeof st);priority_queuepairint,int,vectorpairint,int,greaterpairint,int q;q.push({d[s]0,s});while(q.size()){int uq.top().second;q.pop();if(st[u]) continue;st[u]1;for(int ih[u];i!-1;ine[i]){int ve[i];if(d[v]d[u]w[i]) {d[v]d[u]w[i];q.push({d[v],v});}}}for(int ih[s];i!-1;ine[i]){int ve[i];if(w[i]d[v]) fr[s][v]to[v][s]1;}
}
int solve(int s)
{static int id[N];for(int i1;in;i){pot[i].reset();pot[i].set(i);}for(int i1;in;i) id[i]i;sort(id1,id1n,[](const int i,const int j){return d[s][i]d[s][j];});for(int i1;in;i){int uid[i];for(int ih[u];i!-1;ine[i]){int ve[i];if(d[s][u]w[i]d[s][v]) pot[v]|pot[u];}}for(int i1;in;i)if(d[s][i]0x3f3f3f3f||(pot[i]fr[s]to[i]).count()) fr[s][i]to[i][s]1;return fr[s].count();
}
int main()
{nrd(),mrd();memset(d,0x3f,sizeof d);memset(h,0xff,sizeof h);for(int i1;in;i){fr[i].reset();fr[i][i]1;to[i].reset();to[i][i]1;}while(m--){int urd(),vrd(),crd();add(u,v,c);}for(int i1;in;i) dij(i,d[i]);int ans0;for(int i1;in;i) anssolve(i);printf(%d\n,ans);
}
