UESTC_方老师的分身 II CDOJ 915

方老师的分身 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

Sample Input Sample Output
4 4
1 2 1
2 3 2
1 3 100
3 4 1
1 3 5
7

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 ;
}
上一篇:10个技巧优化PHP程序Laravel 5框架


下一篇:JSP里面九个内置对象