poj1724--ROADS（最短路变形）

本文主要是介绍poj1724--ROADS（最短路变形），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点击打开链接

题目大意：给出n个点，m条路径（有向），每条边有一个花费和一个长度，要求在给定的花费内求1到n的最短路径

用dis[i][j]表示从1到i点，花费为j的最短路径，跑spfa，求出最短路

#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std ;
#define INF 0x3f3f3f3f
struct nn{int v , l , t ;int next ;
}edge[20000];
struct node{int u , t ;
}p , q ;
int head[110] , cnt ;
int dis[110][11000] , vis[110][11000] ;
queue <node> que ;
void add(int u,int v,int l,int t) {edge[cnt].v = v ; edge[cnt].l = l ;edge[cnt].t = t ;edge[cnt].next = head[u] ; head[u] = cnt++ ;
}
int main() {int k , n , m , i ;int u , v , l , t , min1 ;while( scanf("%d %d %d", &k, &n, &m) != EOF ) {memset(head,-1,sizeof(head)) ;memset(dis,INF,sizeof(dis)) ;memset(vis,0,sizeof(vis)) ;while( !que.empty() ) que.pop() ;cnt= 0 ;while( m-- ) {scanf("%d %d %d %d", &u, &v, &l, &t) ;add(u,v,l,t) ;}dis[1][0] = 0 ;vis[1][0] = 1 ;p.u = 1 ; p.t = 0 ;que.push(p) ;while( !que.empty() ) {p = que.front() ;que.pop() ;vis[ p.u ][ p.t ] = 0 ;for(i = head[ p.u ] ; i != -1 ; i = edge[i].next) {if( p.t+edge[i].t <= k && dis[ p.u ][ p.t ]+edge[i].l < dis[ edge[i].v ][ p.t+edge[i].t ] ) {dis[ edge[i].v ][ p.t+edge[i].t ] = dis[ p.u ][ p.t ] + edge[i].l ;if( !vis[ edge[i].v ][ p.t+edge[i].t ] ) {vis[ edge[i].v ][ p.t+edge[i].t ] = 1 ;q.u = edge[i].v ;q.t = p.t+ edge[i].t ;que.push(q) ;}}}}min1 = INF ;for(i = 0 ; i <= k ; i++)min1 = min(min1,dis[n][i]) ;if( min1 == INF ) min1 = -1 ;printf("%d\n", min1) ;}return 0;
}

这篇关于poj1724--ROADS（最短路变形）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---