emm..我佛了。。。spafa为何这么快。。。这。。QAQ

---

 

The Number of Points in Shortest Path

时间限制：1000MS      内存限制：131072KB

题目描述(points.cpp)

一张图有n个点，由m条带权无向边构成。对于两个点a,b你需要求出所有可能出现在a,b间最短路径上的点（包括a,b）

输入格式(points.in)

第一行n,m表示n个点，m条边

接下来m行，每行3个数a,b,v表示a,b之间有条边权为v的边

接下来一个数q,表示询问的个数

接下来q行，每行两个数a,b,表示询问a,b

输出格式(points.out)

对于每个询问，输出a,b之间最短路径上的点的总个数

数据规模与约定

对于10%的数据，n≤10,

对于50%的数据，n≤100,

对于所有的数据，n≤1000,m≤min(n⋅n/2,10000),q≤5000，1≤v≤10000

注意：由于a到b的最短路可能不止一条，所以所有可能出现在各种最短路上的点都要计入答案！！

考试时floyed硬刚，只有50分。。。

#include<cstdio>
#include<iostream>
#include<cstring>
#define R register int
using namespace std;
inline int g() {
    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
    do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
}
int n,m,q;
int e[1010][1010];
signed main() {
    n=g(),m=g(); memset(e,0x3f,sizeof(e));
    for(R i=1,u,v;i<=m;++i) u=g(),v=g(),e[u][v]=e[v][u]=g();
    for(R i=1;i<=n;++i) e[i][i]=0;
    for(R k=1;k<=n;++k) for(R i=1;i<=n;++i) for(R j=1;j<=n;++j) e[i][j]=min(e[i][j],e[i][k]+e[k][j]);
    q=g(); for(R i=1,u,v;i<=q;++i) {
        u=g(),v=g(); R cnt=0;
        for(R i=1;i<=n;++i) if(e[u][i]+e[i][v]==e[u][v]) ++cnt;
        printf("%d\n",cnt);
    }
}

考完试看题解：

spafa？！

what？！？！？！？

周一，我忽然觉得dijkstra也可以卡过（mlogn,差不多1E+8）。。。然鹅。。。50分。。。

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#define R register int
const int N=1010,M=10010;
using namespace std;
inline int g() {
    R ret=0; register char ch; while(!isdigit(ch=getchar())); 
    do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret;
}
int n,m,t,cnt=1;
int vr[M<<1],nxt[M<<1],w[M<<1],fir[N],d[N][N];
bool vis[N];
priority_queue<pair<int,int> >q;
inline void add(int u,int v,int ww) {vr[++cnt]=v,w[cnt]=ww,nxt[cnt]=fir[u],fir[u]=cnt;}
signed main() {
    freopen("points.in","r",stdin);
    freopen("points.out","w",stdout);
    n=g(),m=g();
    for(R i=1,u,v,w;i<=m;++i) u=g(),v=g(),w=g(),add(u,v,w),add(v,u,w);
    memset(d,0x3f,sizeof(d));
    for(R i=1;i<=n;++i) { memset(vis,0,sizeof(vis));
        q.push(make_pair(0,i)),vis[i]=false; d[i][i]=0;
        while(q.size()) {
            R u=q.top().second; q.pop(); if(vis[u]) continue; vis[u]=true;
            for(R j=fir[u];j;j=nxt[j]) { R v=vr[j];
                if(d[i][v]>d[i][u]+w[j]) d[i][v]=d[i][u]+w[j],q.push(make_pair(-d[i][v],v));
            }
        }
    } t=g();
    for(R i=1,u,v;i<=t;++i) {
        u=g(),v=g(); R ans=0;
        for(R j=1;j<=n;++j) if(d[u][j]+d[j][v]==d[u][v]) ++ans;
        printf("%d\n",ans);
    }
}

好吧。。上spafa。。。what。。。竟然A了。。。我佛了。。。

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#define R register int
using namespace std;
const int N=1010,M=10010;
inline int g() {
    R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix;
    do ret=ret*10+(ch^48); while(isdigit(ch=getchar())); return ret*fix;
}
int n,m,t,cnt=1;
int vr[M<<1],nxt[M<<1],w[M<<1],fir[N],d[N][N];
bool vis[N];
queue<int> q;
inline void add(int u,int v,int ww) {vr[++cnt]=v,w[cnt]=ww,nxt[cnt]=fir[u],fir[u]=cnt;}
signed main() {
    freopen("points.in","r",stdin);
    freopen("points.out","w",stdout);
    n=g(),m=g();
    for(R i=1,u,v,w;i<=m;++i) u=g(),v=g(),w=g(),add(u,v,w),add(v,u,w);
    memset(d,0x3f,sizeof(d));
    for(R i=1;i<=n;++i) {
        d[i][i]=0; q.push(i),vis[i]=true;
        while(q.size()) {
            R u=q.front(); q.pop(); vis[u]=false;
            for(R j=fir[u];j;j=nxt[j]) { R v=vr[j];
                if(d[i][v]>d[i][u]+w[j]) {
                    d[i][v]=d[i][u]+w[j];
                    if(!vis[v]) vis[v]=true,q.push(v);
                }
            }
        }
    } t=g();
    for(R i=1,u,v;i<=t;++i) {  R ans=0;
        u=g(),v=g();
        for(R j=1;j<=n;++j) if(d[u][j]+d[j][v]==d[u][v]) ++ans;
        printf("%d\n",ans);
    }
}

好吧。。。。spafa好。。。（吗？重新认知。。

---

2019.04.22