不知哪个OJ The Number of Points in Shortest Path 最短路。。

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

 

上一篇:C++ 标准库之iomanip


下一篇:c# 远程监控(4) 接收端 RTP包重组 分屏显示