spoj 338

本文主要是介绍spoj 338，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意： 无向图  每条边有长度和费用两个属性  求从点1到点n 在花费不超过 k 的情况下的最短路径

BFS  使用优先队列 长度短的优先出列      题解上的方法没看懂  不知道怎么用链表维护 .....

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>using namespace std;struct node
{int dd, pp, len;node(int d, int p, int le){dd = d, pp = p, len = le;}bool operator < (const node & p) const{if(len != p.len)return p.len < len;return p.pp < pp;}
};
vector<int> gto[110], cost[110], Len[110];
bool vis[110][10010];
int main()
{int T,N,K,R,ans;scanf("%d",&T);while(T--){ans = -1;memset(vis, false, sizeof(vis));scanf("%d%d%d",&K,&N,&R);for(int i = 1; i <= N; i++){gto[i].clear(), cost[i].clear(), Len[i].clear();}for(int i = 0; i < R; i++){int s,d,l,t;scanf("%d%d%d%d",&s,&d,&l,&t);gto[s].push_back(d), Len[s].push_back(l), cost[s].push_back(t);}priority_queue<node> q;q.push(node(1, 0, 0));while(!q.empty()){node u = q.top();q.pop();if(u.dd == N){ans = u.len;break;}if(!vis[u.dd][u.pp]){vis[u.dd][u.pp] = true;int p = gto[u.dd].size();for(int i = 0; i < p; i++){int de = gto[u.dd][i];int _len = u.len + Len[u.dd][i];int co = u.pp + cost[u.dd][i];if(co <= K)q.push(node(de, co, _len));}}}printf("%d\n",ans);}return 0;
}

这篇关于spoj 338的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---