hdu 6201(無方向図最長路)

仮想始点と仮想終点を設定し、各点と始点の間に負のエッジを設定します.値はこの点の本の価値の反対の数(本を買うことを代表してお金を使う)で、各点と終点は1本の正辺で、値はこの点の本の価格(本を売ってお金を稼ぐことを代表します)です.それから図の中であげた辺に従って無方向の辺を建てて、権値は負(道路費を代表します)です.それから最も長い道を走って、spfaは緩和の条件を直します

#include
#include
#include
#include
using namespace std;
const int maxn = 100000+10;
const int inf = 1e9;
int n;
int cost[100000+10];
struct node
{
    int to;
    int w;
    node(int a,int b):to(a),w(b){}
};
vectorG[maxn];
int dist[maxn],vis[maxn];
void spfa()
{
    queueq;
    for(int i=0;i<=n+1;i++) dist[i] = -inf;
    memset(vis,0,sizeof(vis));
    q.push(0); vis[0] = 1; dist[0] = 0;
    while(!q.empty())
    {
        int u = q.front(); q.pop(); int len = G[u].size();
        for(int i=0;i