刚刚打算用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