这题怎么说呢，负环上的点都不行
网上也有很多解法
我用dfs的spfa解的
我发现网上别人的代码都是用bfs的spfa写的，我就用的dfs的，快了好多
代码还看的别人的，只有中间的spfa是自己写的
我自己原来写的不知道为什么就过不了
把别人的spfa换成自己的就过了
这个是ac的：
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
using namespace std; const int N = ;
const int MAX = 0x3f3f3f3f;
int dis[N];
int p[N];
int h[N];
int cnt[N];
bool vis[N];
bool r[N];
int c[N]; struct Node
{
int u, v, w, next;
}e[N*N]; void dfs(int x)
{
r[x] = ;
for(int i=h[x]; i!=-; i=e[i].next)
if(!r[e[i].v])
dfs(e[i].v);
} void spfa(int u)
{
if(r[u])
return ;
vis[u] = true;
for(int i = h[u]; i != -; i = e[i].next)
{
int v,w;
v = e[i].v;
w = e[i].w;
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u]+w;
if(vis[v])
{
dfs(v);
return ;
}
else
{
spfa(v);
}
}
}
vis[u] = false;
} int main()
{
int T;
scanf("%d", &T);
for(int tt=; tt<=T; tt++)
{
int n, m;
scanf("%d", &n);
memset(cnt, , sizeof(cnt));
memset(vis, , sizeof(vis));
memset(r, , sizeof(r));
memset(dis, 0x3f3f3f3f, sizeof(dis));
for(int i=; i<=n; i++)
scanf("%d", &p[i]);
scanf("%d", &m);
memset(h, -, sizeof(h));
for(int i=; i<m; i++)
{
int a, b;
scanf("%d%d", &a, &b);
e[i].u = a;
e[i].v = b;
e[i].w = (p[b]-p[a])*(p[b]-p[a])*(p[b]-p[a]);
e[i].next = h[a];
h[a] = i;
}
int Q;
scanf("%d", &Q);
for(int i=; i<Q; i++)
scanf("%d", &c[i]);
printf("Case %d:\n", tt); dis[] = ;
spfa();
for(int i=; i<Q; i++)
{
int to = c[i];
if(dis[to]==MAX || r[to] || dis[to] < )
printf("?\n");
else
printf("%d\n", dis[to]);
}
}
return ;
}
这个是wa的，那位dalao帮我抓抓虫啊，真的苦，我看了半天楞是没看出来
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = ;
const int INF = 0x3f3f3f3f;
int n,m;
int cnt;
struct node
{
int v,w;
};
bool vis[maxn];
int head[maxn];
int nex[maxn];
node e[maxn*maxn];
int dis[maxn];
int busy[maxn];
bool vis2[maxn];
int c[maxn];
void adde(int u,int v,int w)
{
node t;
t.v = v;
t.w = w;
e[cnt] = t;
nex[cnt] = head[u];
head[u] = cnt ++;
}
void spfa(int u);
void dfs(int u);
int main()
{
int t;
scanf("%d",&t);
for(int k = ; k <= t; ++k)
{
memset(vis2,,sizeof(vis2));
memset(dis,0x3f,sizeof(dis));
memset(vis,,sizeof(vis));
memset(head,-,sizeof(head));
//memset(cn,0,sizeof(cn));
memset(nex,-,sizeof(nex));
memset(e,,sizeof(e));
cnt = ;
scanf("%d",&n);
for(int i = ; i <= n; ++i)
scanf("%d",busy+i); scanf("%d",&m);
for(int i = ; i < m; ++i)
{
int a,b;
scanf("%d%d",&a,&b);
int c = (busy[b] - busy[a])*(busy[b] - busy[a])*(busy[b] - busy[a]);
adde(a,b,c);
}
int Q;
scanf("%d",&Q);
for(int i = ; i < Q; ++i)
scanf("%d",c+i); printf("Case %d:\n", k);
dis[] = ;
spfa();
for(int i = ; i < Q; ++i)
{
if(dis[c[i]] == INF || vis2[c[i]] || dis[c[i]] < )
printf("?\n");
else
printf("%d\n",dis[c[i]]);
}
}
return ;
}
void spfa(int u)
{
if(vis2[u])
return ;
vis[u] = true;
for(int i = head[u]; i != -; i = nex[i])
{
int v,w;
v = e[i].v;
w = e[i].w;
if(dis[v] > dis[u] + w)
{
dis[v] = dis[u]+w;
if(vis[v])
{
dfs(v);
return ;
}
else
{
spfa(v);
}
}
}
vis[u] = false;
}
void dfs(int u)
{
vis2[u] = true;
for(int i = head[u]; i != -; i = nex[i])
{
int v = e[i].v;
if(vis2[v] == false)
dfs(v);
}
}