夢追い人

"It takes a dreamer to make a dream come true."―Vincent Willem van Gogh

なんか溜まってきた・・・

Djkstraばっかっですが・・・

0117

#include <cstdio>
#include <vector>
#include <climits>
#include <queue>
#include <functional>
using namespace std;
struct edge { 
    int to, cost;
    edge(int _to, int _cost) { to = _to; cost = _cost; }
};
typedef pair<int, int> P;
void solve() {
    int T, N;
    scanf("%d%d",&N,&T);
    vector<edge> G[N];
    int d[N];
    for (int i=0; i<T; i++) {
        int x, y, c1, c2;
        scanf("%d%*c%d%*c%d%*c%d", &x,&y,&c1,&c2);
        G[x-1].push_back(edge(y-1,c1));
        G[y-1].push_back(edge(x-1,c2));	
    }
    int start, goal, gift, cost;
    scanf("%d%*c%d%*c%d%*c%d",&start,&goal,&gift,&cost);
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d+N, INT_MAX);
    d[start-1] = 0;
    que.push(P(0,start-1));
    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        for (int i=0; i<G[v].size(); i++) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
    int res = gift-cost-d[goal-1];
    fill(d, d+N, INT_MAX);
    d[goal-1] = 0;
    que.push(P(0,goal-1));
    while (!que.empty()) {
        P p = que.top(); que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        for (int i=0; i<G[v].size(); i++) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
    printf("%d\n", res-d[start-1]);
}
int main() {
    solve();
}

0200

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <functional>
#include <queue>
#include <climits>
using namespace std;
typedef pair<int, int> P;
struct train {
int to, cost;
train(int _to, int _cost) { to=_to; cost=_cost; }
};
int n,m,k,a,b,r;
void djk(vector<train> G[], int s, int g) {
	int d[m];
	fill(d, d+m, INT_MAX);
	d[s-1] = 0;
	priority_queue<P, vector<P>, greater<P> > que;
	que.push(P(0,s-1));
	while(!que.empty()) {
		P p = que.top(); que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;
        for (int i=0; i<G[v].size(); i++) {
            train e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
	}
	printf("%d\n",d[g-1]);
}
int main() {
	while (scanf("%d%d",&n,&m)) {
		if (n==0&&m==0) break;
		vector<train> mcost[m], mtime[m];
		for (int i=0; i<n; i++) {
			int c, t;
			scanf("%d%d%d%d",&a,&b,&c,&t);
			mcost[a-1].push_back(train(b-1,c));
			mcost[b-1].push_back(train(a-1,c));
			mtime[a-1].push_back(train(b-1,t));
			mtime[b-1].push_back(train(a-1,t));
		}
		scanf("%d",&k);
		for (int i=0; i<k; i++) {
			scanf("%d%d%d",&a,&b,&r);
			if (r) djk(mtime,a,b);
			else djk(mcost,a,b);
		}
	}
}

0226

#include <iostream>
using namespace std;
int main() {
	string a, b;
	while (cin>>a>>b) {
		if (a=="0"&&b=="0") break;
		int hit=0, blow=0;
		for (int i=0; i<4; i++) {
			if (a[i]==b[i]) {
				hit++;
			} else {
				for (int j=0; j<4; j++) {
					if (a[i]==b[j]) blow++;
				}
			}
		}
		cout << hit << " " << blow << endl;
	}
}

0123

#include <cstdio>
int main() {
	float fm, tm;
	while (scanf("%f%f",&fm,&tm)!=EOF) {
		if (fm<35.5&&tm<71.0) printf("AAA\n");
		else if (fm<37.5&&tm<77.0) printf("AA\n");
		else if (fm<40.0&&tm<83.0) printf("A\n");
		else if (fm<43.0&&tm<89.0) printf("B\n");
		else if (fm<50.0&&tm<105.0) printf("C\n");
		else if (fm<55.0&&tm<116.0) printf("D\n");
		else if (fm<70.0&&tm<148.0) printf("E\n");
		else printf("NA\n");
	}
}