提出 #63416685

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
const int N=90,S=1<<9;
typedef long long ll;
#define mkp make_pair


int n,k;
ll f[N][N][S];
bool vis[N];
priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > >q;
ll dis[N][N];

void dij(int st,int s)
{
    for(int i=1;i<=n;i++) vis[i]=0;
    for(int i=1;i<=n;i++) q.push(mkp(f[st][i][S],i));
    while(!q.empty())
    {
        auto t=q.top(); q.pop();
        int u=t.second;
        if(vis[u]) continue;
        vis[u]=1;
        for(int j=1;j<=n;j++)
        {
            int v=j; ll w=dis[u][v];
            if(f[st][v][s]>f[st][u][s]+w)
            {
                f[st][v][s]=f[st][u][s]+w;
                if(!vis[v]) q.push(mkp(f[st][v][s],v));   
            }
        }
    }
}
int Q;
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) 
        for(int j=1;j<=n;j++) scanf("%lld",&dis[i][j]);
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    
    memset(f,0x3f,sizeof(f));
    for(int u=1;u<=n;u++)
    {
        f[u][u][1<<k]=0;
        for(int i=1;i<=k;i++) f[u][i][(1<<(i-1))]=0;
        for(int s=1;s<(1<<(k+1));s++)
        {
            for(int msk=s;msk;msk=(msk-1)&s)
                for(int i=1;i<=n;i++)
                    f[u][i][s]=min(f[u][i][s],f[u][i][msk]+f[u][i][msk^s]);
            dij(u,s);
        }
    }
    scanf("%d",&Q); int u,v;
    int full=(1<<(k+1))-1;
    while(Q--)
    {
        scanf("%d%d",&u,&v);
        ll ans=0x3f3f3f3f3f3f3f3f;
        for(int i=1;i<=n;i++) ans=min(ans,f[u][i][full]+dis[i][v]);
        printf("%lld\n",ans);
    }
}

提出情報

コンパイルエラー

Main.cpp: In function ‘int main()’:
Main.cpp:38:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   38 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
Main.cpp:40:36: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   40 |         for(int j=1;j<=n;j++) scanf("%lld",&dis[i][j]);
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:59:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   59 |     scanf("%d",&Q); int u,v;
      |     ~~~~~^~~~~~~~~
Main.cpp:63:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   63 |         scanf("%d%d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~
Main.cpp: In function ‘void dij(int, int)’:
Main.cpp:17:48: warning: array subscript 512 is above array bounds of ‘ll [512]’ {aka ‘long long int [512]’} [-Warray-bounds]
   17 |     for(int i=1;i<=n;i++) q.push(mkp(f[st][i][S],i));
      |                                      ~~~~~~~~~~^
Main.cpp:9:4: note: while referencing ‘f’
    9 | ll f[N][N][S];
      |    ^

ジャッジ結果