跳至正文

USACO 3.2.6 Sweet Butter 解题报告

  • OI路程

刚刚打算用O(n^3)的算法,但超时百分百,马上就转型,用SPFA,每个节点用一次SPFA不会超时,因为这是一个稀疏图,800个节点却最多1450个,太给力了,每个节点用一次SPFA,然后判断是否为最优解,如此就够了,代码: / LANG: C ID: yylogoo1 PROG: butter / #include #include int n, p, c; int cows[500]; int map[801][800]; int link[801][800]; int count[800]; int dis[801][801]; void add(int a, int b, int c) { link[a][count[a]] = b; map[a][count[a]] = c; count[a]++; } #define MAX 1000 int queue[MAX]; int used[801]; int rear, head; void enqueue(int n) { int t; if(used[n]){ return; } used[n] = 1; t = (rear + 1) % MAX; assert(t != head); queue[rear] = n; rear = t; } int exqueue(void) { int t; assert(rear != head); t = queue[head]; used[t] = 0; head = (head + 1) % MAX; return t; } #define INF 0xFFFFFF long long ans = INF; void srch(int s) { int i, j, t; enqueue(s); while(rear != head){ t = exqueue(); for(i = 0; i dis[s][t] + map[t][i]){ dis[s][j] = dis[s][t] + map[t][i]; enqueue(j); } } } } int main(void) { int i, j; long long t; int a, b, d; freopen("butter.in", "r", stdin); freopen("butter.out", "w", stdout); scanf("%d%d%d", &n, &p, &c); for(i = 0; i 0){ srch(i); for(j = t = 0; j

发表回复

您的电子邮箱地址不会被公开。