方老师的分身 II

Time Limit: 10000/5000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

Submit Status

方老师计算出了走路时间最长的那个分身所用的时间。于是有个特殊的分身（据说是方老师真身！）就不想如此古板的走最短路了！由于这个分身的特殊性，这个分身对于单向边可以当双向边走。但是这个特殊的分身想走最短路的同时，要求至少经过k条边。

Input

有多组数据

第一行两个整数n，m（1≤n≤5000，1≤m≤100000）表示有n个教室，m条边。

接下来m行，每行3个数，u，v，t。表示u，v间有一条长度为t的边。

最后一行三个整数s，t，k，表示起点、终点、至少经过k（k≤50）条边。

Output

一个整数，表示最短路径长度。如果无解输出−1。

每组数据占一行。

Sample input and output

Source

2014 UESTC Training for Graph Theory

解题报告：

还是跑SPFA,不过加了个经过的边数。。其他的跟SPFA一样的..

#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <vector>

#include <queue>

#define pb push_back

using namespace std;

const int maxn = 5e3 + ;

int mincost[maxn][+];

bool inqueue[maxn][+];

typedef struct Edge

{

  int target,cost;

  Edge(int target ,int cost)

   {

      this->target = target , this->cost = cost;

   }

};

typedef struct status

{

  int pos,step;

  status(int pos,int step)

   {

         this->pos = pos , this->step = step;

   }

};

queue<status>q;

vector<Edge>E[maxn];

int n,m,st,ed,k;

void bfs()

{

   mincost[st][] = ;

   q.push(status(st,));

   while(!q.empty())

    {

       int pos = q.front().pos , step = q.front().step ; q.pop();

       int thiscost = mincost[pos][step];

       inqueue[pos][step] = false;

       for(int i =  ; i < E[pos].size() ; ++ i)

        {

           int nextnode = E[pos][i].target;

           int thisstep = min(,step+);

           if (mincost[nextnode][thisstep] == - || mincost[nextnode][thisstep] > thiscost + E[pos][i].cost)

            {

                mincost[nextnode][thisstep] = thiscost + E[pos][i].cost;

                if (!inqueue[nextnode][thisstep])

                 {

                     q.push(status(nextnode,thisstep));

                     inqueue[nextnode][thisstep] = true;

                 }

            }

        }

    }

}

int main(int argc,char *argv[])

{

  while(~scanf("%d%d",&n,&m))

   {

         memset(mincost,-,sizeof(mincost));

         memset(inqueue,false,sizeof(inqueue));

         for(int i =  ; i <= m ; ++ i)

          {

                int u,v,t;

                scanf("%d%d%d",&u,&v,&t);

                E[u].pb(Edge(v,t));

                E[v].pb(Edge(u,t));

       }

      scanf("%d%d%d",&st,&ed,&k);

      bfs();

      int ans = mincost[ed][k];

      for(int i = k +  ; i <=  ; ++ i)

       if (mincost[ed][i] != -)

        {

            if (ans == -)

             ans = mincost[ed][i];

            ans = min (ans , mincost[ed][i]);

        }

      printf("%d\n",ans);

         for(int i =  ; i <= n ; ++ i)

          E[i].clear();

   }

  return ;

}