AOJ 0212 Highway Express Bus

これは良問だと思った。
これを機にダイクストラ法の理解が一層深まった気がする。
解説
まず、下のコードではdpテーブルはdとおいて、d[0][i]に普通のダイクストラ法をやっていく。その後にmin(~,~)で割引券を使った時と使ってない時を判定して、最短経路を求めていく。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>

using namespace std;
typedef pair<int, int> P;

const int INF = 1 << 30;

struct edge {int to, cost; };

int V;
int d[100][100];

vector<edge> G[100];
priority_queue<P, vector<P>, greater<P> > que;

void dijkstra(int s,int a){
  for(int i = 0; i < V; i++) d[a][i] = INF;
  que.push(P(0, s));
  d[a][s] = 0;

  while(!que.empty()){
    P p = que.top(); que.pop();
    int v = p.second;
    if(d[a][v] < p.first) continue;
    for(int i = 0; i < G[v].size(); i++){
      edge e = G[v][i];
      int Min = (a == 0 ? d[a][v] + e.cost : min(d[a][v] + e.cost, d[a-1][v] + e.cost/2));
      if(d[a][e.to] > Min){
        d[a][e.to] = Min;
        que.push(P(d[a][e.to], e.to));
      }
    }
  }
}

int main(){
  int c,m,s,e,From,To,Cost;
  edge E;
  while(scanf("%d%d%d%d%d",&c,&V,&m,&s,&e)!=EOF,c|V|m|s--|e--){
    for(int i = 0; i < m; i++){
      scanf("%d%d%d",&From,&To,&Cost);
          
      From--,To--;
      E.to = From,E.cost = Cost;
      G[To].push_back(E);
      E.to = To;
      G[From].push_back(E);
    }
    
    for(int i = 0; i <= c; i++) dijkstra(s, i);
    
    printf("%d\n",d[c][e]);
    
    for(int i = 0; i < 100; i++) G[i].clear();
  }
}

POJ 2707 Copier Reduction

解説
サンプルセット見た感じだと、多分縮小の問題だと思うのでそのまま実装

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int f(double a, double b){
  return (int)(b/a*100);
}

int main(){
  int l,r;
  double a,b,c,d;
  while(cin >> a >> b >> c >> d, a && b && c && d){
    
    l = f(min(a,b),min(c,d));
    r = f(max(a,b),max(c,d));
    
    cout << ((l > r ? r : l) < 100 ? (l > r ? r : l): 100)<< '%' << endl;
  }
}

三項演算子で無駄な書き方をしているので反省

(l < 100 && r < 100 ?  (l > r ? r : l) : 100)

いや〜でもコード量的にはそんなこともなかったか...

今日

今日は全然PKUしなかったし全然頭を使わなかったので反省。学校の課題をするのと本を読んでいました。

ゼロから学ぶベクトル解析 (ゼロから学ぶシリーズ)

とりあえず今日はこの本を読んでいました...。が、微分をあんまり学習してなかったせいか、全然読めませんでした...。本当にダメダメだ。

GCの本

ガベージコレクションのアルゴリズムと実装

まだちょっとしか読んでないのですが、GCアルゴリズム詳細解説ここと合わせて読むと尚Goodだと思います。っていうか授業とかで実行時メモリ構造とか教えてくれないんかねー...。

POJ 2656 Unhappy Jinjin

下にコードが書いてあるなーとか思ってたら答えだったので萎えぽよ〜

a,b,d,v,i;main(n){while(scanf("%d",&n),n){v=-1;for(i=1;i<=n;i++){scanf("%d%d",&a,&b);if(a+b>v)v=a+b,d=i;}if(v<=8)puts("0");else printf("%d\n",d);}}

POJ 2578 Keep on Truckin'

short codingっぽいようななにか。もっと工夫できると思うけどお馬鹿な脳をしているので全く思いつかない。

i,h[3];main(){scanf("%d%d%d",h+0,h+1,h+2);for(;i<3;i++){if(h[i]<168){printf("CRASH %d\n",h[i]);break;}else if(i==2)puts("NO CRASH");}}

POJ 2521 How much did the businessman lose

解説
いくら損したか（問題分全然読んでないので適当）

main(n,m,p,c){while(scanf("%d%d%d%d",&n,&m,&p,&c),n)printf("%d\n",n-m+p);}

scanfとても面白い。%*[フォーマット指定子]で引数を取らない入力になるとは...