本文共 1850 字，大约阅读时间需要 6 分钟。

乍一看，发现自己有好几篇博客都木有写了，唉。

Input

256 7 8 9 1061 22 33 41 55 44 5245101 2 4 4 5 6 7 8 9 10101 22 33 11 44 55 66 77 88 99 1023 10

output

这道题主要运用了Bellman-ford算法，和SPFA

所谓Bellman-ford算法的讲解，继续扒图

课堂上的PPT，很详细

所以对于本题涅

题意：图解，用测试数据第一组做例子，因为本题是有向图，所以会出现负环的问题用SPFA处理此类问题。那么本题DFS遍历路径，然后就是起点是1，从1开始，到其他的点，比如1到4，税费最少是1~2~3~4，所以是3，针对每一个点，在spfa的基础上dfs找它的路径，最后得出正确结果。

感觉我的解释好混乱，还是写一篇spfa笔记好了

#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;const int maxn=1e5;const int Inf=1e8;int T,N,M,W,P,a,b,tot,tag;//T组数据 ,N点数,M道路数,W询问个数 ，P 税费 int head[maxn],vis[maxn],dis[maxn],ary[maxn],inq[maxn],cnt[maxn];struct edge{
       int to,next,w;};edge e[maxn*2];queue
       
         Q;void add_edge(int u, int v, int w){
   //链式前向星     e[++tot].to = v;    e[tot].w = w;    e[tot].next = head[u];    head[u] = tot;}void dfs(int lop){
   //dfs递归遍历边  vis[lop]=1; for(int i=head[lop];i!=-1;i=e[i].next){
     if(vis[e[i].to]==0) dfs(e[i].to); }}void spfa(){
    dis[1]=0;inq[1]=1;Q.push(1);//起点 while(Q.size()){
     int u=Q.front();Q.pop();  inq[u]=0;  if(vis[u]) continue;  for(int i=head[u];i!=-1;i=e[i].next){
      int v=e[i].to;   if(dis[v]>dis[u]+e[i].w){
       cnt[v]=cnt[u] + 1;    dis[v]=dis[u] + e[i].w;    if(cnt[v]>=N) dfs(v);    if(!inq[v]){
        Q.push(v);     inq[v]=1;    }   }  } } }int main(){
    ios::sync_with_stdio(false); cin>>T;tag=1; while(T--){
     cin>>N;tot=0;  //初始化  for(int i=1;i<=N;i++) dis[i]=Inf;  memset(inq,0,sizeof(inq));memset(head,-1,sizeof(head));  memset(cnt,0,sizeof(cnt));memset(vis,0,sizeof(vis));  for(int i=1;i<=N;i++)   cin>>ary[i];  cin>>M;  for(int i=1;i<=M;i++){
      cin>>a>>b;   int tmp=ary[b]-ary[a];   add_edge(a,b,pow(tmp,3));  }  spfa();  cin>>W;  cout<<"Case "<
        
         <<":"<
         
          >P; if(dis[P]<3||dis[P]==Inf||vis[P]==1) cout<<"?"<
         
        
       
      
     
    
   

转载地址：http://udwzi.baihongyu.com/