WUPC 2012

Submission #645261

Source codeソースコード

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(i=0;i<n;++i)
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define mp make_pair
#define pb push_back
#define fi first
#define sc second

struct edge{ int to,cost; };
typedef pair<int,int> pi;
typedef pair<pi,int> pii;

const int INF=1000000000;

vector<edge> G[1000];

int main(int argc, char const *argv[]) {
  int i;

  int n,m;
  scanf(" %d %d",&n,&m);
  rep(i,m){
    int f,t,c;
    scanf(" %d %d %d",&f,&t,&c);
    G[f].pb(edge{t,c});
    G[t].pb(edge{f,c});
  }

  priority_queue<pii,vector<pii>,greater<pii>>que;

  int d4[1000][4];
  fill(d4[0],d4[1000],INF);
  d4[0][0]=0;
  que.push(pii(pi(0,0),0));
  while(!que.empty()){
    pii p=que.top();
    que.pop();
    int v=p.fi.sc;
    if(d4[v][p.sc]<p.fi.fi) continue;
    rep(i,G[v].size()){
      edge e=G[v][i];
      if(d4[e.to][(p.sc+e.cost)%4]>d4[v][p.sc]+e.cost){
        d4[e.to][(p.sc+e.cost)%4]=d4[v][p.sc]+e.cost;
        if(e.to!=n-1){
          que.push(pii(pi(d4[e.to][(p.sc+e.cost)%4],e.to),(p.sc+e.cost)%4));
        }
      }
    }
  }

  int d7[1000][7];
  fill(d7[0],d7[1000],INF);
  d7[0][0]=0;
  que.push(pii(pi(0,0),0));
  while(!que.empty()){
    pii p=que.top();
    que.pop();
    int v=p.fi.sc;
    if(d7[v][p.sc]<p.fi.fi) continue;
    rep(i,G[v].size()){
      edge e=G[v][i];
      if(d7[e.to][(p.sc+e.cost)%7]>d7[v][p.sc]+e.cost){
        d7[e.to][(p.sc+e.cost)%7]=d7[v][p.sc]+e.cost;
        if(e.to!=n-1){
          que.push(pii(pi(d7[e.to][(p.sc+e.cost)%7],e.to),(p.sc+e.cost)%7));
        }
      }
    }
  }

  printf("%d\n",min(d4[n-1][0],d7[n-1][0]));
  return 0;
}

Submission

Task問題 E - 会場への道
User nameユーザ名 imulan
Created time投稿日時
Language言語 C++11 (GCC 4.8.1)
Status状態 AC
Score得点 100
Source lengthソースコード長 1760 Byte
File nameファイル名
Exec time実行時間 40 ms
Memory usageメモリ使用量 1460 KB

Compiler messageコンパイルメッセージ

./Main.cpp: In function ‘int main(int, const char**)’:
./Main.cpp:24:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf(" %d %d",&n,&m);
^
./Main.cpp:27:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf(" %d %d %d",&f,&t,&c);
^

Test case

Set

Set name Score得点 / Max score Cases
sub1 30 / 30 sub1/input_0.txt,sub1/input_1.txt,sub1/input_2.txt,sub1/input_20.txt,sub1/input_21.txt,sub1/input_22.txt,sub1/input_23.txt,sub1/input_24.txt,sub1/input_3.txt,sub1/input_4.txt,sub1/input_5.txt,sub1/input_6.txt,sub1/input_7.txt,sub1/input_8.txt,sub1/input_9.txt
sub2 70 / 70 sub2/input_0.txt,sub2/input_1.txt,sub2/input_10.txt,sub2/input_11.txt,sub2/input_12.txt,sub2/input_13.txt,sub2/input_14.txt,sub2/input_15.txt,sub2/input_16.txt,sub2/input_17.txt,sub2/input_18.txt,sub2/input_19.txt,sub2/input_2.txt,sub2/input_20.txt,sub2/input_21.txt,sub2/input_22.txt,sub2/input_23.txt,sub2/input_24.txt,sub2/input_25.txt,sub2/input_3.txt,sub2/input_4.txt,sub2/input_5.txt,sub2/input_6.txt,sub2/input_7.txt,sub2/input_8.txt,sub2/input_9.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sub1/input_0.txt AC 26 ms 840 KB
sub1/input_1.txt AC 25 ms 872 KB
sub1/input_2.txt AC 27 ms 784 KB
sub1/input_20.txt AC 29 ms 996 KB
sub1/input_21.txt AC 28 ms 876 KB
sub1/input_22.txt AC 28 ms 916 KB
sub1/input_23.txt AC 27 ms 872 KB
sub1/input_24.txt AC 27 ms 920 KB
sub1/input_3.txt AC 26 ms 924 KB
sub1/input_4.txt AC 26 ms 924 KB
sub1/input_5.txt AC 27 ms 924 KB
sub1/input_6.txt AC 26 ms 924 KB
sub1/input_7.txt AC 26 ms 924 KB
sub1/input_8.txt AC 24 ms 928 KB
sub1/input_9.txt AC 27 ms 876 KB
sub2/input_0.txt AC 27 ms 924 KB
sub2/input_1.txt AC 27 ms 868 KB
sub2/input_10.txt AC 26 ms 924 KB
sub2/input_11.txt AC 37 ms 1256 KB
sub2/input_12.txt AC 35 ms 1304 KB
sub2/input_13.txt AC 27 ms 920 KB
sub2/input_14.txt AC 34 ms 1248 KB
sub2/input_15.txt AC 37 ms 1260 KB
sub2/input_16.txt AC 40 ms 1460 KB
sub2/input_17.txt AC 37 ms 1248 KB
sub2/input_18.txt AC 37 ms 1256 KB
sub2/input_19.txt AC 37 ms 1392 KB
sub2/input_2.txt AC 27 ms 876 KB
sub2/input_20.txt AC 28 ms 1004 KB
sub2/input_21.txt AC 27 ms 876 KB
sub2/input_22.txt AC 27 ms 916 KB
sub2/input_23.txt AC 26 ms 924 KB
sub2/input_24.txt AC 27 ms 924 KB
sub2/input_25.txt AC 27 ms 928 KB
sub2/input_3.txt AC 26 ms 924 KB
sub2/input_4.txt AC 26 ms 924 KB
sub2/input_5.txt AC 25 ms 920 KB
sub2/input_6.txt AC 26 ms 920 KB
sub2/input_7.txt AC 26 ms 924 KB
sub2/input_8.txt AC 27 ms 872 KB
sub2/input_9.txt AC 26 ms 920 KB