大意不再赘述。
思路:挺简单的一道题,开始我是想保存一个节点的前驱节点,然后判断当最短路相等时再判断cost[fa[y]][y] 与cost[x][y]的大小,然后用tot加上它,后来WA。细想一下,原来它们以前的tot可能不相等,即我们必须以节点为单位保存一个节点在最短路上的最小费用,这样才能保证求出正确的结果。顺便贴下以前关键的代码。
AC CODE
#include <iostream> #include <cstdlib> #include <cstdio> #include <cstring> #include <string> using namespace std; const int MAXN = 1010; const int MAXM = 10010; const int INF = 0x3f3f3f3f; int w[MAXN][MAXN]; int d[MAXN]; int value[MAXN][MAXN]; int cost[MAXN]; int fa[MAXN]; int n, m; int s, e; void init() { memset(w, INF, sizeof(w)); memset(cost, 0, sizeof(cost)); memset(value, 0, sizeof(value)); } void Dijkstra(int src, int end) { bool vis[MAXN] = {0}; for(int i = 1; i <= n; i++) d[i] = (i == src)? 0:INF; for(int i = 1; i <= n; i++) fa[i] = i; for(int i = 1; i <= n; i++) { int x, m = INF; for(int y = 1; y <= n; y++) if(!vis[y] && m > d[y]) m = d[x=y]; vis[x] = 1; for(int y = 1; y <= n; y++) if(d[y] >= d[x] + w[x][y]) { if(d[y] == d[x] + w[x][y]) { if(cost[y] > cost[x] + value[x][y]) { cost[y] = cost[x] + value[x][y]; fa[y] = x; } } else { d[y] = d[x] + w[x][y]; cost[y] = cost[x] + value[x][y]; fa[y] = x; } } } printf("%d %d\n", d[end], cost[end]); } int read_case() { init(); scanf("%d%d", &n, &m); if(!n && !m) return 0; while(m--) { int u, v, w1, p; scanf("%d%d%d%d", &u, &v, &w1, &p); if(w[u][v] > w1) { w[u][v] = w[v][u] = w1; value[u][v] = value[v][u] = p; } } scanf("%d%d", &s, &e); } int main() { while(read_case()) { Dijkstra(s, e); } return 0; }
WA CODE
void Dijkstra(int src, int end) { bool vis[MAXN] = {0}; int tot = 0; for(int i = 1; i <= n; i++) d[i] = (i == src)? 0:INF; for(int i = 1; i <= n; i++) fa[i] = i; for(int i = 1; i <= n; i++) { int x, m = INF, p = INF; for(int y = 1; y <= n; y++) if(!vis[y] && m >= d[y]) m = d[x=y]; vis[x] = 1; for(int y = 1; y <= n; y++) if(d[y] >= d[x] + w[x][y]) { if(d[y] == d[x] + w[x][y]) { if(cost[fa[y]][y] > cost[x][y]) { tot += (cost[x][y]-cost[fa[y]][y]); fa[y] = x; } } else { d[y] = d[x] + w[x][y]; tot += cost[x][y]; fa[y] = x; } } } printf("%d %d\n", d[end], tot); }