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しなかったし全然頭を使わなかったので反省。学校の課題をするのと本を読んでいました。
- 作者: 西野友年
- 出版社/メーカー: 講談社
- 発売日: 2002/04/26
- メディア: 単行本(ソフトカバー)
- 購入: 1人 クリック: 31回
- この商品を含むブログ (5件) を見る
GCの本
- 作者: 中村成洋,相川光,竹内郁雄
- 出版社/メーカー: 秀和システム
- 発売日: 2010/03/17
- メディア: 単行本
- 購入: 25人 クリック: 810回
- この商品を含むブログ (94件) を見る
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とても面白い。%*[フォーマット指定子]で引数を取らない入力になるとは...