結果

問題 No.340 雪の足跡
ユーザー kotatsugame
提出日時 2020-02-23 17:41:03
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 719 ms / 1,000 ms
コード長 1,259 bytes
コンパイル時間 787 ms
コンパイル使用メモリ 78,920 KB
実行使用メモリ 71,168 KB
最終ジャッジ日時 2024-10-10 05:18:07
合計ジャッジ時間 10,748 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 | main()
      | ^~~~

ソースコード

diff #
プレゼンテーションモードにする

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
int W,H,N;
int cx[1000][1001],cy[1000][1001];
vector<int>G[1<<20];
int dist[1<<20];
main()
{
    cin>>W>>H>>N;
    for(;N--;)
    {
        int M;cin>>M;
        int u;cin>>u;
        for(;M--;)
        {
            int v;cin>>v;
            if(u%W==v%W)
            {
                if(u<v)
                {
                    cy[u%W][u/W]++;
                    cy[u%W][v/W]--;
                }
                else
                {
                    cy[u%W][u/W]--;
                    cy[u%W][v/W]++;
                }
            }
            else
            {
                if(u<v)
                {
                    cx[u/W][u%W]++;
                    cx[u/W][v%W]--;
                }
                else
                {
                    cx[u/W][u%W]--;
                    cx[u/W][v%W]++;
                }
            }
            u=v;
        }
    }
    for(int i=0;i<W;i++)
    {
        for(int j=0;j<H-1;j++)
        {
            cy[i][j+1]+=cy[i][j];
            if(cy[i][j]>0)
            {
                int u=j*W+i,v=j*W+W+i;
                G[u].push_back(v);
                G[v].push_back(u);
            }
        }
    }
    for(int i=0;i<H;i++)
    {
        for(int j=0;j<W-1;j++)
        {
            cx[i][j+1]+=cx[i][j];
            if(cx[i][j]>0)
            {
                int u=i*W+j,v=i*W+j+1;
                G[u].push_back(v);
                G[v].push_back(u);
            }
        }
    }
    for(int i=1;i<H*W;i++)dist[i]=1e9;
    queue<int>P;P.push(0);
    while(!P.empty())
    {
        int u=P.front();P.pop();
        for(int v:G[u])
        {
            int nxt=dist[u]+1;
            if(dist[v]>nxt)
            {
                dist[v]=nxt;
                P.push(v);
            }
        }
    }
    if(dist[H*W-1]<1e9)cout<<dist[H*W-1]<<endl;
    else cout<<"Odekakedekinai.."<<endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0