题意

C国有n座城市，城市之间通过m条单向道路连接。一条路径被称为最短路，当且仅当不存在从它的起点到终点的另外一条路径总长度比它小。两条最短路不同，当且仅当它们包含的道路序列不同。我们需要对每条道路的重要性进行评估，评估方式为计算有多少条不同的最短路经过该道路。现在，这个任务交给了你。
n≤1500、m≤5000、w≤10000，答案模1e9+7。

分析

sb题。枚举起点跑最短路，然后把最短路DAG建出来瞎dp一下就好了。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
const int N=1500;
const int MOD=1000000007;
const int inf=1000000000;
int n,m,cnt,last[N],ls[N],dis[N],deg[N],a[N],f[N],g[N],ans[5005];
struct edge{int to,from,w,next,nx,use;}e[5005];
queue<int> que;
bool vis[N];
int read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
void updata(int &x,int y) {x+=y;x-=x>=MOD?MOD:0;}
void addedge(int u,int v,int w)
{
e[++cnt].from=u;e[cnt].to=v;e[cnt].w=w;e[cnt].next=last[u];last[u]=cnt;
e[cnt].nx=ls[v];ls[v]=cnt;
}
void topusort()
{
for (int i=1;i<=n;i++) if (!deg[i]) que.push(i);
int a1=0;
for (int i=1;i<=n;i++)
{
int u=que.front();que.pop();a[++a1]=u;
for (int i=last[u];i;i=e[i].next)
if (e[i].use)
{
deg[e[i].to]--;
if (!deg[e[i].to]) que.push(e[i].to);
}
}
}
void spfa(int s)
{
for (int i=1;i<=n;i++) dis[i]=inf,deg[i]=f[i]=0,g[i]=1;
dis[s]=0;que.push(s);vis[s]=1;
while (!que.empty())
{
int u=que.front();que.pop();
for (int i=last[u];i;i=e[i].next)
if (dis[u]+e[i].w<dis[e[i].to])
{
dis[e[i].to]=dis[u]+e[i].w;
if (!vis[e[i].to]) vis[e[i].to]=1,que.push(e[i].to);
}
vis[u]=0;
}
for (int i=1;i<=m;i++)
{
int x=e[i].from,y=e[i].to;e[i].use=0;
if (dis[x]+e[i].w==dis[y]) e[i].use=1,deg[y]++;
}
topusort();
f[s]=1;
for (int i=1;i<=n;i++)
for (int j=last[a[i]];j;j=e[j].next)
if (e[j].use) updata(f[e[j].to],f[a[i]]);
for (int i=n;i>=1;i--)
for (int j=ls[a[i]];j;j=e[j].nx)
if (e[j].use) updata(g[e[j].from],g[a[i]]);
}
int main()
{
n=read();m=read();
for (int i=1;i<=m;i++)
{
int x=read(),y=read(),z=read();
addedge(x,y,z);
}
for (int i=1;i<=n;i++)
{
spfa(i);
for (int j=1;j<=m;j++)
if (e[j].use) updata(ans[j],(LL)f[e[j].from]*g[e[j].to]%MOD);
}
for (int i=1;i<=m;i++) printf("%dn",ans[i]);
return 0;
}

最后

以上就是凶狠招牌为你收集整理的bzoj 2750: [HAOI2012]Road 最短路+dp题意分析代码的全部内容，希望文章能够帮你解决bzoj 2750: [HAOI2012]Road 最短路+dp题意分析代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。