bzoj5056: OI遊戲

我們van♂遊戲233。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
queue<int> q;
int read()
{
    char ch=getchar();int f=;
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){f=(f<<)+(f<<)+ch-'0';ch=getchar();}
    return f;
}
struct node
{
    int from;
    int to;
    int next;
    int w;
}edge[];
int tot1=,head[],n,m,dis[];bool vis[];char s[];
const int mod=;
void add(int u,int v,int w)
{
    edge[tot1].from=u;
    edge[tot1].to=v;
    edge[tot1].w=w;
    edge[tot1].next=head[u];
    head[u]=tot1++;
}
void spfa()
{
    q.push();
    dis[]=;
    while(!q.empty())
    {
        int x=q.front();
        q.pop();vis[x]=;
        for(int i=head[x];i!=-;i=edge[i].next)
        {
            if(dis[edge[i].to]>dis[x]+edge[i].w)
            {
                dis[edge[i].to]=dis[x]+edge[i].w;
                if(!vis[edge[i].to])
                {
                    q.push(edge[i].to);
                    vis[edge[i].to]=;
                }
            }
        }
    }
}
void solve()
{
    long long ans=;
    for(int i=;i<=n;i++)
    {
        long long tot=;
        for(int j=head[i];j!=-;j=edge[j].next)
        {
            if((long long)dis[i]==(long long)dis[edge[j].to]+(long long)edge[j].w) tot++;
        }
        //cout<<tot<<" ";
        ans=ans*tot%mod;
    }
    cout<<ans;
}
int main()
{
    memset(head,-,sizeof(head));
    memset(dis,,sizeof(dis));
    n=read();
    for(int i=;i<=n;i++)
    {
        scanf("%s",s+);
        for(int j=;j<=n;j++)
        {
            if(s[j]!='0')
            {
                add(i,j,s[j]-'0');
            }
        }
    }
    spfa();
    //for(int i=1;i<=n;i++)
    //cout<<dis[i]<<" ";
    solve();
}