10
23
2015
1

BZOJ1006:[HNOI2008]神奇的国度

 

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
vector <int> g[10001];
int n, m, ans = 0, sum[10001], list[10001], color[10001], hash[10001];
bool mark[10001];
void init() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) g[i].clear();
	for (int i = 1, x, y; i <= m; i++) {
		scanf("%d%d", &x, &y);
		g[x].push_back(y);
		g[y].push_back(x);
	}
}
int main() {
	init();
	for (int i = n; i; i--) {
		int t = 0;
		for (int j = 1; j <= n; j++)
			if (!mark[j] && sum[j] >= sum[t]) t = j;
		mark[t] = true; list[i] = t;
		for (int j = 0; j < g[t].size(); j++)
			sum[g[t][j]]++;
	}
	for (int i = n; i; i--) {
		int t = list[i];
		for (int j = 0; j < g[t].size(); j++) hash[color[g[t][j]]] = i;
		int j;
		for (j = 1; ; j++) if (hash[j] != i) break;
		color[t] = j;
		if (j > ans) ans = j;
	}
	printf("%d\n", ans);
	return 0;
}
10
13
2015
2

BZOJ1002:[FJOI2007]轮状病毒

 

#include <cstdio>
#include <cstring>
#define MAXN 1010
using namespace std;
 
struct BigInteger {
    int a[MAXN];
    const static int L = 1000;
     
    BigInteger() {
        memset(a, 0, sizeof(a)); 
    }
};
 
BigInteger f[1010][2];
int n;
     
    BigInteger Init(int N) {
        BigInteger ans;
        for (int i = 1; i <= ans.L; i++) {
            ans.a[i] = N % 10;
            N /= 10;
            if (N == 0) break;
        }
        return ans;
    }
     
    BigInteger Plus(BigInteger A, BigInteger B) {
        BigInteger ans;
        int k = 0;
        for (int i = 1; i <= ans.L; i++) {
            ans.a[i] = A.a[i] + B.a[i] + k;
            k = ans.a[i] / 10, ans.a[i] %= 10;
        }
        return ans;
    }
     
    BigInteger Minus(BigInteger A, BigInteger B) {
        BigInteger ans;
        for (int i = 1; i <= ans.L; i++) ans.a[i] = A.a[i];
        for (int i = 1; i <= ans.L; i++) {
            ans.a[i] -= B.a[i];
            if (ans.a[i] < 0) { ans.a[i] += 10, ans.a[i + 1]--; }
        }
        return ans;
    }
     
    BigInteger Times(BigInteger A, int B) {
        BigInteger ans;
        for (int i = 1; i <= ans.L; i++) {
            ans.a[i] += A.a[i] * B;
            if (ans.a[i] > 9) {
                ans.a[i + 1] += ans.a[i] / 10;
                ans.a[i] %= 10;
            }
        }
        return ans;
    }
     
    void Print(BigInteger A) {
        int flag = 0;
        for (int i = A.L; i >= 1; i--) {
            if (flag) printf("%d", A.a[i]);
            else if (A.a[i] > 0) {
                printf("%d", A.a[i]);
                flag = 1;
            }
        }
        if (flag == 0) printf("0");
        printf("\n");
    }
     
    void Prepare() {
        f[0][1] = Init(1);
        f[1][1] = Init(1), f[1][0] = Init(1);
    }
     
int main() {
    scanf("%d", &n);
    Prepare();
    for (int i = 2; i < n; i++) {
        f[i][0] = Plus(f[i - 1][0], f[i - 1][1]);
        f[i][1] = Plus(f[i][0], f[i - 1][1]);
    }
    BigInteger ans;
    for (int i = 1; i <= n; i++) ans = Plus(ans, Times(Times(f[n - i][1], i), i));
    Print(ans);
    return 0;
}
Category: BZOJ | Tags: 递推 高精度
9
10
2015
3

NOIP2012提高组

D1T1 vigenere密码

  维吉尼亚方表是个好东西,多表替代相比神奇的单表替代的凯撒密码什么的是差距大了去了。随机性分析也是无效的。手工的话只有猜密钥位数攻击了。然并卵。

  模拟大法好啊,觉得自己还是写的比较漂亮的。

#include <cstdio>
#include <cstring>
int n, m;
char key[101], arr[1001];

inline int solve(int a, int b) {
	return (a + (26 - b)) % 26;
}

int main() {
	scanf("%s", key); m = strlen(key);
	scanf("%s", arr); n = strlen(arr);
	for (int i = 0; i < n; i++) {
		int t;
		if ('a' <= key[i % m] && key[i % m] <= 'z') t = key[i % m] - 'a';
			else t = key[i % m] - 'A';
		if ('a' <= arr[i] && arr[i] <= 'z')
			printf("%c", (char) ('a' + solve(arr[i] - 'a', t)));
		else
			printf("%c", (char) ('A' + solve(arr[i] - 'A', t)));
	}
	printf("\n");
	return 0;
}

D2T2 国王游戏

  贪心+高精度。正确性证明我拉一段。

假设相邻的两个人左右手分别是(a, b), (A, B)。设a * b <= A * B,i之前所有人的左手乘积为S。
则,ans1 = max{S / b, S * a / B}
若交换
则,ans2 = max{S / B, S * A / b}
因为,a * b <= A * B
所以,S * a / B <= S * A / b
又因为,S / B <= S * a / B
所以,ans2 = S * A / b
ans1 = max{S / B[i], S * a / B}
所以,ans1 <= ans2
证毕

  自己写的高精度乘单精度一开始返回大数的位数判错了,后来改对了。

#include <algorithm>
#include <cstring>
using std :: sort;
struct Sec {
	int a, b;
} sec[1001], king;
struct bignum {
	int l, a[5000];
	
	bignum () {
		l = 1; memset(a, 0, sizeof(a));
	}
	
	bignum (int n) {
		l = 0; memset(a, 0, sizeof(a));
		while (n) {
			a[++l] = n % 10; n /= 10;
		}
	}
};
int n;

bool cmp(Sec x, Sec y) {
	if (x.a * x.b < y.a * y.b) return true;
		else return false;
}

bignum operator + (bignum A, bignum B) {
	bignum ret;
	ret.l = A.l > B.l ? A.l : B.l;
	for (int i = 1; i <= ret.l; i++) {
		ret.a[i] += A.a[i] + B.a[i];
		if (ret.a[i] > 9)
			ret.a[i + 1]++, ret.a[i] -= 10;
	}
	if (ret.a[ret.l + 1]) ret.l++;
	return ret;
}

bignum operator / (bignum A, int B) {
	bignum ret;
	int cnt = 0;
	for (int i = A.l; i >= 1; i--) {
		cnt += A.a[i];
		if (cnt >= B) {
			ret.a[i] = cnt / B;
			cnt %= B;
		}
		cnt *= 10;
	}
	ret.l = A.l;
	while (ret.a[ret.l] == 0 && ret.l > 1) ret.l--;
	return ret;
}

bignum operator * (bignum A, int B) {
	bignum ret; ret.l = A.l;
	for (int i = 1; i <= A.l; i++) {
		ret.a[i] += A.a[i] * B;
		int k = i;
		while (ret.a[k] > 9) {
			ret.a[k + 1] += ret.a[k] / 10; ret.a[k++] %= 10;
		}
		if (k > ret.l) ret.l = k;
	}
	return ret;
}

bool operator > (bignum A, bignum B) {
	if (A.l != B.l) return A.l > B.l;
	for (int i = A.l; i >= 1; i--) {
		if (A.a[i] > B.a[i]) return 1;
		if (A.a[i] < B.a[i]) return 0;
	}
	return 0;
}

void print(bignum A) {
	for (int i = A.l; i >= 1; i--) printf("%d", A.a[i]);
	printf("\n");
}

int main() {
	scanf("%d", &n);
	scanf("%d%d", &king.a, &king.b);
	for (int i = 1; i <= n; i++)
		scanf("%d%d", &sec[i].a, &sec[i].b);
	sort(sec + 1, sec + n + 1, cmp);
	bignum tmp = king.a, ans = 0;
	for (int i = 1; i <= n; i++) {
		bignum k = tmp / sec[i].b;
		if (k > ans) ans = k;
		tmp = tmp * sec[i].a;
	}
	print(ans);
	return 0;
}
Category: 未分类 | Tags: NOIP 提高组 2012
9
9
2015
2

双高精度除法代码

贴段代码。高精度除高精度,P党什么的最有爱了。

var
	a, b, c : array[0..40000] of longint;
	i, j, k, l, m, n, lena, lenb, lenc : longint;
	s : ansistring;

function mo(w : longint) : boolean;
var
	i : longint;
begin
	if lena - w + 1 > lenb then exit(true);
	if lena - w + 1 < lenb then exit(false);
	for i := 0
 to lenb - 1 do
	begin
		if a[lena - i] > b[lenb - i] then exit(true);
		if a[lena - i] < b[lenb - i] then exit(false);
	end;
	mo := true;
end;

procedure minus(w : longint);
var
	i, j : longint;
begin
	j := 1;
	for i := w to w + lenb - 1 do
	begin
		if a[i] < b[j] then
		begin
			dec(a[i + 1]);
			inc(a[i],10 - b[j]);
		end else dec(a[i],b[j]);
		inc(j);
	end;
	while (lena > 0) and (a[lena] = 0) do dec(lena);
	if lena = 0 then lena := 1;
end;

begin
	readln(s);
	lena := length(s);
	for i := 1 to lena do a[lena - i + 1] := ord(s[i]) - 48;
	readln(s);
	lenb := length(s);
	for i := 1 to lenb do b[lenb - i + 1] := ord(s[i]) - 48;
	
	lenc := lena - lenb + 1;
	for i := lenc downto 1 do
		while mo(i) do
		begin
			minus(i);
			inc(c[i]);
		end;
	while (lenc > 0) and (c[lenc] = 0) do dec(lenc);
	if lenc = 0 then lenc := 1;
	
	for i:=lenc downto 1 do write(c[i]);
end.
Category: 未分类 | Tags:
9
3
2015
2

NOIP提高组2011

D1T1 铺地毯

#include <cstdio>
const int MAXN = 100001;
int n, x, y, a[MAXN], b[MAXN], g[MAXN], k[MAXN];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d%d%d%d", &a[i], &b[i], &g[i], &k[i]);
	scanf("%d%d", &x, &y);
	int ans = 0;
	for (int i = 1; i <= n; i++)
		if (a[i] <= x && x <= a[i] + g[i] && b[i] <= y && y <= b[i] + k[i])
			ans = i;
	printf("%d\n", ans);
	return 0;
}

D1T2 选择客栈

#include<cstdio>
using namespace std;
int f[200001], sav[200001], ans[200001], num[200001];
int n, p, k, cnt = 0;

int main() {
    scanf("%d%d%d", &n, &k, &p);
    for (int i = 1; i <= n; i++) {
		int color, cost;
		scanf("%d%d", &color, &cost);
		if (cost <= p) f[i] = f[i - 1] + 1; 
    		else f[i] = f[i - 1];
    	if (sav[color] == 0) {
        	sav[color] = i; num[color]++; continue;
    	}
      	if (f[i] - f[sav[color] - 1] > 0) ans[i] = num[color];
      		else ans[i] = ans[sav[color]];
      	sav[color] = i;
      	num[color]++;
    }   
    for (int i = 1; i <= n; i++) cnt += ans[i];
    printf("%d\n", cnt);
    return 0;
}

D1T3 Mayan游戏

    Mayan游戏写起来比较棘手,做法的话,就是上DFS。有两个剪枝操作:某种颜色存在但是个数小于3没法消除;如果一个方块左边也是方块就不必左移,因为右移效果一样字典序更小。

#include <cstdio>
#include <cstdlib>
#include <cstring>
void swap(int &a, int &b) {
	int c = a; a = b; b = c;
}

int n;

struct map {
	int a[5][7];
	bool d[5][7];
	
	void Read() {
		memset(a, 0, sizeof(a));
		memset(d, 0, sizeof(d));
		for (int i = 0; i < 5; i++) {
			int t1, t2 = 0;
			scanf("%d", &t1);
			while (t1) {
				a[i][t2++] = t1; scanf("%d", &t1);
			}
		}
	}
	
	void Falldown(int i) {
		int pop = 0;
		for (int j = 0; j < 7; j++)
			if (a[i][j]) {
				a[i][pop++] = a[i][j];
				if (j >= pop) a[i][j] = 0;
			}
	}
	
	void Fall() {
		for (int i = 0; i < 5; i++) Falldown(i);
	}
	
	bool Combo() {
		memset(d, 0, sizeof(d)); bool ret = 0;
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 7; j++) {
				if (a[i][j] == 0) continue;
				
				if (0 < i && i < 4)
					if (a[i - 1][j] == a[i][j] && a[i][j] == a[i + 1][j]) {
						d[i - 1][j] = d[i][j] = d[i + 1][j] = 1;
						ret = 1;
					}
				if (0 < j && j < 6)
					if (a[i][j - 1] == a[i][j] && a[i][j] == a[i][j + 1]) {
						d[i][j - 1] = d[i][j] = d[i][j + 1] = 1;
						ret = 1;
					}
			}
		return ret;
	}
	
	void Collapse() {
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 7; j++)
				if (d[i][j]) a[i][j] = 0;
		memset(d, 0, sizeof(d));
	}
	
	void Move(int i, int j, int k) {
		swap(a[i][j], a[i + k][j]);
		Falldown(i), Falldown(i + k);
		while (Combo()) {
			Collapse(); Fall();
		}
	}
	
	bool Empty() {
		for (int i = 0; i < 5; i++)
			if (a[i][0]) return 0;
		return 1;
	}
	
	int GetMin() {
		int cnt[11] = {0};
		for (int i = 0; i < 5; i++)
			for (int j = 0; j < 7; j++)
				if (a[i][j]) cnt[a[i][j]]++;
		int min = 35;
		for (int i = 1; i <= 10; i++)
			if (cnt[i] && cnt[i] < min) min = cnt[i];
		return min;
	}
} sta;

struct Node {
	int a, b, c;
	
	void Load(int A, int B, int C) {
		a = A, b = B, c = C;
	}
} ans[100];
	
void dfs(int t) {
	if (sta.Empty()) {
		for (int i = 1; i <= t; i++)
			printf("%d %d %d\n", ans[i].a, ans[i].b, ans[i].c);
		exit(0);
	}
	if (t == n) return;
	if (sta.GetMin() <= 2) return;
	map bak = sta;
	for (int i = 0; i < 5; i++)
		for (int j = 0; j < 7; j++) {
			if (sta.a[i][j] == 0) continue;
			if (i < 4 && sta.a[i][j] != sta.a[i + 1][j]) {
				ans[t + 1].Load(i, j, 1); sta.Move(i, j, 1);
				dfs(t + 1);
				sta = bak;
			}
			if (i > 0 && sta.a[i - 1][j] == 0) {
				ans[t + 1].Load(i, j, -1); sta.Move(i, j, -1);
				dfs(t + 1);
				sta = bak;
			}
		}
}
	
int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	scanf("%d", &n);
	sta.Read();
	dfs(0);
	printf("-1\n");
	return 0;
}

D2T1 计算系数

    杨辉三角就可以了~

#include <cstdio>
#include <algorithm>
const int M = 10007;
using namespace std;

int f[1001][1001];
int a, b, k, n, m;

int main() {
	long long ans = 1;
	scanf("%d%d%d%d%d", &a, &b, &k, &n, &m);
	f[1][1] = f[1][2] = 1;
	for (int i = 2; i <= k; i++) 
		for (int j = 1; j <= i + 1; j++)
			f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % M;
	ans = f[k][m + 1];
	for (int i = 1; i <= n; i++) ans = (ans * a) % M;
	for (int j = 1; j <= m; j++) ans = (ans * b) % M;
	printf("%d", ans);
	return 0;
}

D2T2 聪明的质检员

    二分法计算就可以了。P.S.VIJOS是windows评测,我一开始%lld没过,然并卵

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;

long long n, m, S, w[200001], v[200001], l[200001], r[200001], arr[200001];
long long sum1[200001], sum2[200001];

long long fun(int k) {
	long long ret = 0;
	for (int i = 1; i <= n; i++) {
		if (w[i] >= k) {
			sum1[i] = sum1[i - 1] + 1;
			sum2[i] = sum2[i - 1] + v[i];
		} else {
			sum1[i] = sum1[i - 1];
			sum2[i] = sum2[i - 1];
		}
	}
	for (int i = 1; i <= m; i++)
		ret += (sum1[r[i]] - sum1[l[i] - 1]) * (sum2[r[i]] - sum2[l[i] - 1]);
	return S - ret;
}

long long find(int L, int R) {
	if (L == R) return abs(fun(L));
	long long M = (L + R) / 2; 
	long long tmp = fun(arr[M]);
	long long ret = abs(tmp);
	if (tmp > 0) ret = min(find(L, M), ret);
		else if (tmp < 0) ret = min(find(M + 1, R), ret);
	return ret;
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	scanf("%I64d%I64d%I64d", &n, &m, &S);
	for (int i = 1; i <= n; i++){
		scanf("%I64d%I64d", &w[i], &v[i]);
		arr[i] = w[i];
	}
	sort(arr + 1, arr + n + 1);
	for (int i = 1; i <= m; i++)
		scanf("%I64d%I64d", &l[i], &r[i]);    
	long long ans = find(1, n);
	printf("%I64d", ans);
	return 0;
}

D2T3 观光公交

    易见每个旅客上车时间都已固定,答案取决于下车时间,所以得出贪心操作正确性。然后就是每次氮气都用在在车上人最多的时候。

#include <cstdio>
int n, m, k, t, a, b;
int d[1001], lim[1001], sce[1001], up[1001], down[1001];
	
	int max(int a, int b) { return a > b ? a : b; }
	
int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int p = 0;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i < n; i++) scanf("%d", &d[i]);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &t, &a, &b);
		up[a]++, down[b]++;
		sce[a] = max(sce[a], t);
		p += t;
	}
	for (int i = 1; i <= n; i++)
		lim[i] = max(lim[i - 1], sce[i - 1]) + d[i - 1];
	while (k--) {
		int cnt = 0, _max = 0, t = 0;
		for (int i = n; i > 1; i--) {
			if (lim[i] <= sce[i]) cnt = 0;
			cnt += down[i];
			if (d[i - 1] && cnt > _max) _max = cnt, t = i - 1;
		}
		if (!t) break;
		d[t]--;
		for (int i = t + 1; i <= n; i++)
			lim[i] = max(lim[i - 1], sce[i - 1]) + d[i - 1];
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		lim[i] = max(lim[i - 1], sce[i - 1]) + d[i - 1];
		ans += down[i] * lim[i];
	}
	printf("%d\n", ans - p);
	return 0;
}
Category: 未分类 | Tags: 2011 NOIP 提高组
9
1
2015
2

BZOJ1003:[ZJOI2006]物流运输trans

具体做法是先用SPFA暴力求出dis[i][j](在i-j这段时间始终畅通的最短路),然后用动归做。状态转移式似乎比较简单。

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
struct node {
	int t, v;
};
vector <node> G[21];
const int INF = 1 << 30;
int n, m, k, e, d, D[101][101], f[101];
bool sce[21][101];
bool clo[21];
	
void add(int A, int B, int C) {
	node t1 = {B, C}, t2 = {A, C};
	G[A].push_back(t1), G[B].push_back(t2);
}

void init() {
	scanf("%d%d%d%d", &n, &m, &k, &e);
	for (int i = 1; i <= m; i++) G[i].clear();
	for (int i = 1; i <= e; i++) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		add(x, y, z);
	}
	memset(sce, 0, sizeof(sce));
	scanf("%d", &d);
	for (int i = 1; i <= d; i++) {
		int p, a, b; scanf("%d%d%d", &p, &a, &b);
		for (int j = a; j <= b; j++)
			sce[p][j] = 1;
	}
}

int SPFA() {
	int head = 0, tail = 1, f[1000], dis[1000];
	bool b[21];
	memset(b, 0, sizeof(b));
	for (int i = 1; i <= m; i++) dis[i] = INF;
	b[1] = 1, f[1] = 1, dis[1] = 0;
	while (head < tail) {
		int T = f[++head]; b[T] = 0;
		for (int i = 0; i < G[T].size(); i++)
			if (!clo[G[T][i].t])
			if (dis[T] + G[T][i].v < dis[G[T][i].t]) {
				dis[G[T][i].t] = dis[T] + G[T][i].v;
				if (!b[G[T][i].t]) {
					b[G[T][i].t] = 1; f[++tail] = G[T][i].t;
				}
			}
	}
	return dis[m];
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

	init();
	
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j++) {
			memset(clo, 0, sizeof(clo));
			for (int k = 1; k <= m; k++)
				for (int l = i; l <= j; l++)
					clo[k] = clo[k] || sce[k][l];
			D[i][j] = SPFA();
		}
	f[0] = -k;
	for (int i = 1; i <= n; i++) f[i] = INF;
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			if (D[j][i] != INF && f[j - 1] != INF)
				if (f[j - 1] + D[j][i] * (i - j + 1) + k < f[i])
					f[i] = f[j - 1] + D[j][i] * (i - j + 1) + k;
	printf("%d\n", f[n]);
	return 0;
}
Category: BZOJ | Tags: DP SPFA 最短路
8
31
2015
4

BZOJ1001[BeiJing2006]狼抓兔子

写的时候RE了,然后调了下,发现要在SPFA里改成滚动数组,不然边数比较多会溢出。

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
struct node {
	int t, v;   
};
const int M = 2000001;
int n, m, pn, a[1001][1001][2], D[2000001], f[2000001];
bool b[2000001];
vector <node> G[2000001];
     
void add(int a, int b, int c) {
	node t1 = {b, c}, t2 = {a, c};
	G[a].push_back(t1), G[b].push_back(t2);
}

void init() {
	scanf("%d%d", &n, &m);
	pn = 2;
	for (int i = 1; i < n; i++)
    	for (int j = 1; j < m; j++)
        	for (int k = 0; k <= 1; k++)
            	a[i][j][k] = ++pn;
	for (int i = 1; i <= pn; i++) G[i].clear();
	
	for (int i = 1; i < n; i++) a[i][0][1] = 1;
	for (int i = 1; i < m; i++) a[n][i][1] = 1;
	for (int i = 1; i < n; i++) a[i][m][0] = 2;
	for (int i = 1; i < m; i++) a[0][i][0] = 2;
    
	int tmp;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < m; j++)
			scanf("%d", &tmp), add(a[i - 1][j][0], a[i][j][1], tmp);
	for (int i = 1; i < n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%d", &tmp), add(a[i][j - 1][1], a[i][j][0], tmp);
	for (int i = 1; i < n; i++)
		for (int j = 1; j < m; j++)
			scanf("%d", &tmp), add(a[i][j][0], a[i][j][1], tmp);
}

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	
	init();
	
	int head = 0, tail = 1;
	memset(b, 0, sizeof(b));
	memset(D, 0x3f, sizeof(D));
	D[1] = 0; b[1] = 1; f[1] = 1;
	while (head < tail) {
    	int tmp = f[++head]; b[tmp] = 0;
    	if (head == M) head = 0;
		for (int i = 0; i < G[tmp].size(); i++)
			if (D[G[tmp][i].t] > D[tmp] + G[tmp][i].v) {
				D[G[tmp][i].t] = D[tmp] + G[tmp][i].v;
				if (!b[G[tmp][i].t]) {
					b[G[tmp][i].t] = 1, f[++tail] = G[tmp][i].t;
					if (tail == M) tail = 0;
				}
			}
	}
	printf("%d\n", D[2]);
	return 0;
}
Category: BZOJ | Tags: 最短路 SPFA
8
31
2015
5

猫咪老师

Category: 未分类 | Tags:

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com