這題目和上題目1201一樣，就只改一下權重。
注意一點，這題目邊比較多，哎，我開搭配100*10005，過了。後來想改為循環隊列，沒想到原來while（head < tail） 沒有改為while（head != tail）記過wa了好幾次。
其他沒什麼了。。。
總之記住一個原則，求最小值，>=,求最長路。求最大值，<=，求最短路。這也是這兩道題目學到的經。。。。這個要搞不清楚，那也只是看了別人代碼能懂，但是自己寫不出來。至於證明可以參考acm論文。
代碼：
[cpp]
#include <stdio.h>
#define maxN 10005//最大邊條數
#define inf 0x7fffffff//最大距離
struct Edge
{
int v, w, next;
}edge[4 * maxN];//邊集
int dis[maxN];
bool vis[maxN]; www.2cto.com
int queue[maxN];
int preEdge[maxN];//同一個頂點的前一條邊
int edgeNum,n,maxn;
void addEdge(int u, int v, int w)//添加一條邊
{
edge[edgeNum].v = v;
edge[edgeNum].w = w;
edge[edgeNum].next = preEdge[u];
preEdge[u] = edgeNum ++;
}
void spfa()//spaf算法
{
int head = 0, tail = 1;
for (int i = 0; i <= maxn; ++ i)
{
dis[i] = -inf;
}
queue[head] = 0;
dis[0] = 0;
while (head != tail)
{
int u = queue[head];
vis[u] = true;
for (int p = preEdge[u]; p != 0; p = edge[p].next)
{
int v = edge[p].v;
if (dis[v] < dis[u] + edge[p].w)
{
dis[v] = dis[u] + edge[p].w;
if (!vis[v])
{
vis[v] = true;
queue[tail] = v;
tail ++;
if (tail == maxN)
{
tail = 0;
}
}
}
}
vis[u] = false;
head ++;
if (head == maxN)
{
head = 0;
}
}
}
int main()
{
scanf("%d", &n);
edgeNum = 1;
maxn = 0;
while (n --)
{
int u, v;
scanf("%d%d", &u, &v);
if (v + 1 > maxn)
{
maxn = v + 1;
} www.2cto.com
addEdge(u, v + 1, 2);
}
for (int i = 0; i <= maxn; ++ i)
{
addEdge(i, i + 1, 0);
addEdge(i + 1, i, -1);
}
spfa();
printf("%d\n", dis[maxn]);
return 0;
}
作者：zhang20072844
