@hsxrr
2017-02-26T14:58:30.000000Z
字数 8560
阅读 716
Dijkstra bellmax-frod floyd
题意
寻找最短的从商店到赛场的路线
思路
无向边的 Dijkstra算法
AC代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 110;
const int INF = 0x3f3f3f3f;
struct Edges{
int form,to,dist;
Edges(int u , int v , int d):form(u),to(v),dist(d){}
};
struct HeapNode{
int d,u;
bool operator < (const HeapNode& rhs) const{
return d > rhs.d;
}
};
struct Dijkstra{
int n,m;
vector<Edges> edges;
vector<int> G[N];
bool done[N];
int d[N],p[N];
void init(int n){
this->n = n;
for(int i = 0 ; i <= n ; i++) G[i].clear();
edges.clear();
}
void AddEdge(int from,int to, int dist){
edges.push_back(Edges(from,to,dist));
m = edges.size();
G[from].push_back(m-1);
}
void dijikstra(int s){
priority_queue<HeapNode> Q;
for(int i = 0 ; i <= n ; i++) d[i] = INF;
d[s] = 0;
memset(done,0,sizeof(done));
Q.push((HeapNode){0,s});
while( !Q.empty() ){
HeapNode x = Q.top();Q.pop();
int u = x.u;
if(done[u]) continue;
done[u] = true;
for(int i = 0 ; i < G[u].size() ; i++){
Edges& e = edges[G[u][i]];
if( d[e.to] > d[u] + e.dist ){
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
Q.push((HeapNode){d[e.to],e.to});
}
}
}
}
};
Dijkstra ans;
int main(){
int n,m,a,b,c;
while( scanf("%d%d",&n,&m) != EOF && n ){
ans.init(n);
for(int i = 0 ; i < m ; i++){
scanf("%d%d%d",&a,&b,&c);
ans.AddEdge(a,b,c);
ans.AddEdge(b,a,c);
}
ans.dijikstra(1);
printf("%d\n",ans.d[n]);
}
return 0;
}
题意
一个人想要通过虫洞打破时间，回到过去，现在有很多虫洞，每个虫洞都有一个起点和终点，穿过虫洞需要一定的时间，如果时间为正，则为双向边，为负为单向边，现在问你是否能够回到过去
题意
其实可以转译为是否存在负环，如果存在就可以回到过去，否则不能回到过去，可以用Bellman_ford算法
AC代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f;
struct Edges{
int form,to,dist;
Edges(int u , int v , int d):form(u),to(v),dist(d){}
};
struct Bellman_ford{
int n,m;
vector<Edges> edges;
vector<int> G[N];
bool done[N];
int d[N],p[N],cnt[N];
bool inq[N];
void init(int n){
this->n = n;
for(int i = 0 ; i <= n ; i++) G[i].clear();
edges.clear();
}
void AddEdge(int from,int to, int dist){
edges.push_back(Edges(from,to,dist));
m = edges.size();
G[from].push_back(m-1);
}
bool bellman_ford(int s){
queue<int> Q;
memset(inq,0,sizeof(inq));
memset(cnt,0,sizeof(cnt));
for(int i = 0 ; i <= n ; i++) d[i] = INF;
d[s] = 0;
inq[s] = true;
Q.push(s);
while( !Q.empty() ){
int u = Q.front();Q.pop();
inq[u] = false;
for(int i = 0 ; i < G[u].size() ; i++){
Edges& e = edges[G[u][i]];
if( d[u] < INF && d[e.to] > d[u] + e.dist ){
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
if( !inq[e.to] ){
Q.push(e.to);
inq[e.to] = true;
if( ++cnt[e.to] > n ) return false;
}
}
}
}
return true;
}
};
Bellman_ford b;
int main(){
int t,n,m,w,form,to,dist;
scanf("%d",&t);
while( t-- ){
scanf("%d%d%d",&n,&m,&w);
b.init(n);
for(int i = 0 ; i < m ; i++){
scanf("%d%d%d",&form,&to,&dist);
b.AddEdge(form,to,dist);
b.AddEdge(to,form,dist);
}
for(int i = 0 ; i < w ; i++){
scanf("%d%d%d",&form,&to,&dist);
b.AddEdge(form,to,-dist);
}
if( !b.bellman_ford(1) ) printf("YES\n");
else printf("NO\n");
}
return 0;
}
题意
有m个经纪人，每个人经纪人都有一定的传播途径，在获得信息后传播给其他经纪人，其传播的总时间为最大传播时间，现在把一个信息传给某一个经纪人使得信息能够在最短时间内传播给所有经济人，并求出最短时间
思路
Floyd算法算出每个人传播给每个人的最短传播时间，然后便利每个人的最长时间，在能过传播给所有人的人中选择时间最短的就是答案（PS：测试数据并没有存在传不到的数据
AC代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 103;
const int INF = 0x3f3f3f3f;
int d[N][N];
void floyd(int n){
for(int k = 1 ; k <= n ; k++)
for(int i = 1 ; i <= n ; i++)
for(int j = 1 ; j <= n ; j++)
if( d[i][j] > d[i][k] + d[k][j] )
d[i][j] = d[i][k]+d[k][j];
}
int main(){
int n,m,a,b;
while( scanf("%d",&n) != EOF && n ){
for(int i = 1 ; i <= n ; i++){
for(int j = 1 ; j <= n ; j++){
if( i == j ) d[i][j] = 0;
else d[i][j] = INF;
}
}
for(int i = 1 ; i <= n ; i++){
scanf("%d",&m);
while( m-- ){
scanf("%d%d",&a,&b);
d[i][a] = b;
}
}
floyd(n);
int ansmin = INF , nowmin = 0 , ans_id = -1;
for(int i = 1 ; i <= n ; i++){
nowmin = 0;
bool ok = true;
for(int j = 1 ; j <= n && ok ; j++){
if( i == j ) continue;
if( d[i][j] == INF ){
ok = false;
}
if( nowmin < d[i][j] ){
nowmin = d[i][j];
}
}
if( !ok ){
continue;
}
if( ansmin > nowmin ){
ansmin = nowmin;
ans_id = i;
}
}
if( ans_id == -1 )
printf("disjoint\n");
else
printf("%d %d\n",ans_id,ansmin);
}
return 0;
}
题意
一个外来的冒险家想要娶一个地位为w的人的女儿，可是这个人需要p金币的嫁妆，但是可以给你提供一些物品，如果你用这个物品兑换，可以给你优惠，但是地位差距相差m以上不能之间或者间接交易，也就是说你购买了w1地位人的物品，就不能与地位在w1+m以上或者w1-m以下的人交易
思路
建立一个边，并且每次便利的时候记录下当前点能交易最高地位与最低地位,如果压入边的时候多判断到达了一个地位不合的点就不算这条边即可，其他的正常的Dijkstra算法
AC代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <map>
#include <set>
using namespace std;
const int N = 103;
const int INF = 1e8 + 7;
typedef long long LL;
struct node{
int val , dw , tdp;
vector<pair<int,int> > v;
}P[N];
struct Edge{
int form,to,dist;
Edge(int u,int v,int d):form(u),to(v),dist(d){}
};
struct HeapNode{
int d,u;
bool operator < (const HeapNode&rhs) const{
return d > rhs.d;
}
};
struct Dijkstra{
int n,m;
vector<Edge> edges;
vector<int> G[N];
bool done[N];
int d[N],p[N];
void init(int n){
this->n = n;
for(int i = 0 ; i <= n ; i++) G[i].clear();
edges.clear();
}
void AddEdge(int form,int to,int dist){
edges.push_back(Edge(form,to,dist));
m = edges.size();
G[form].push_back(m-1);
}
void dijkstra(int s,int dw_min,int dw_max){
priority_queue<HeapNode> Q;
for(int i = 0 ; i <= n ; i++) d[i] = INF;
d[s] = 0;
memset(done,0,sizeof(done));
Q.push((HeapNode){0,s});
while( !Q.empty() ){
HeapNode x = Q.top();Q.pop();
int u = x.u;
if( done[u] ) continue;
done[u] = true;
for(int i = 0 ; i < G[u].size() ; i++){
Edge& e = edges[G[u][i]];
if( d[e.to] > d[u] + e.dist && P[e.to].dw >= dw_min && P[e.to].dw <= dw_max){
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
Q.push((HeapNode){d[e.to],e.to});
}
}
}
}
};
Dijkstra d;
int main(){
int n,m,a,b;
pair<int,int> temp;
while( scanf("%d%d",&m,&n) != EOF ){
d.init(n);
for(int i = 1 ; i <= n ; i++){
scanf("%d%d%d",&P[i].val,&P[i].dw,&P[i].tdp);
d.AddEdge(0,i,P[i].val);
for(int k = 0 ; k < P[i].tdp ; k++){
scanf("%d%d",&temp.second,&temp.first);
P[i].v.push_back(temp);
d.AddEdge(temp.second,i,temp.first);
//d.AddEdge(i,temp.second,temp.first);
}
}
int ans = INF;
for(int i = 1 ; i <= n ; i++){
if( abs( P[i].dw - P[1].dw ) > m ) continue;
d.dijkstra(0,max(P[i].dw,P[1].dw) - m ,max(P[i].dw,P[1].dw) );
ans = min(ans,d.d[1]);
}
printf("%d\n",ans);
}
return 0;
}
题意
给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。
思路
Dijkstra算法中加入一个花费p,记录最短路花费，如果当前的路同样是最短路，则在比较花费，看下花费是否更低即可
AC代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <map>
#include <set>
using namespace std;
const int N = 1003;
const int INF = 1e8 + 7;
typedef long long LL;
struct Edge{
int form,to,dist,cout;
Edge(int u,int v,int d,int c):form(u),to(v),dist(d),cout(c){}
};
struct HeapNode{
int d,c,u;
bool operator < (const HeapNode&rhs) const{
return d == rhs.d ? c > rhs.c : d > rhs.d;
}
};
struct Dijkstra{
int n,m;
vector<Edge> edges;
vector<int> G[N];
//bool done[N];
int d[N],p[N],q[N];
void init(int n){
this->n = n;
for(int i = 0 ; i <= n ; i++) G[i].clear();
edges.clear();
}
void AddEdge(int form,int to,int dist,int cout){
edges.push_back(Edge(form,to,dist,cout));
m = edges.size();
G[form].push_back(m-1);
}
void dijkstra(int s){
priority_queue<HeapNode> Q;
for(int i = 0 ; i <= n ; i++) d[i] = INF , q[i] = INF;
d[s] = 0;q[s] = 0;
//memset(done,0,sizeof(done));
Q.push((HeapNode){0,0,s});
while( !Q.empty() ){
HeapNode x = Q.top();Q.pop();
int u = x.u;
/*if( done[u] ) continue;
done[u] = true;//*/
for(int i = 0 ; i < G[u].size() ; i++){
Edge& e = edges[G[u][i]];
if( d[e.to] > d[u] + e.dist ){
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
q[e.to] = q[u] + e.cout;
Q.push((HeapNode){d[e.to],q[e.to],e.to});
}else if( d[e.to] == d[u] + e.dist && q[e.to] > q[u] + e.cout ){
q[e.to] = q[u] + e.cout;
p[e.to] = G[u][i];
Q.push((HeapNode){d[e.to],q[e.to],e.to});
}
}
}
}
};
Dijkstra d;
int main(){
int n,m,x,y,z,cout;
while( scanf("%d%d",&n,&m) != EOF && n ){
d.init(n);
for(int i = 0 ; i < m ; i++){
scanf("%d%d%d%d",&x,&y,&z,&cout);
d.AddEdge(x,y,z,cout);
d.AddEdge(y,x,z,cout);
}
scanf("%d%d",&x,&y);
d.dijkstra(x);
printf("%d %d\n",d.d[y],d.q[y]);
}
return 0;
}
题意
对于给定的一个起点集合，求起点中到达终点的最短路
思路
翻转图，把其实位置都翻转就可以直接求出终点到达那个起点的路最短即为答案
AC代码
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 1007;
const int INF = 0x3f3f3f3f;
struct Edges{
int form,to,dist;
Edges(int u , int v , int d):form(u),to(v),dist(d){}
};
struct HeapNode{
int d,u;
bool operator < (const HeapNode& rhs) const{
return d > rhs.d;
}
};
struct Dijkstra{
int n,m;
vector<Edges> edges;
vector<int> G[N];
bool done[N];
int d[N],p[N];
void init(int n){
this->n = n;
for(int i = 0 ; i <= n ; i++) G[i].clear();
edges.clear();
}
void AddEdge(int from,int to, int dist){
edges.push_back(Edges(from,to,dist));
m = edges.size();
G[from].push_back(m-1);
}
void dijikstra(int s){
priority_queue<HeapNode> Q;
for(int i = 0 ; i <= n ; i++) d[i] = INF;
d[s] = 0;
memset(done,0,sizeof(done));
Q.push((HeapNode){0,s});
while( !Q.empty() ){
HeapNode x = Q.top();Q.pop();
int u = x.u;
if(done[u]) continue;
done[u] = true;
for(int i = 0 ; i < G[u].size() ; i++){
Edges& e = edges[G[u][i]];
if( d[e.to] > d[u] + e.dist ){
d[e.to] = d[u] + e.dist;
p[e.to] = G[u][i];
Q.push((HeapNode){d[e.to],e.to});
}
}
}
}
};
Dijkstra d;
int main(){
int n,m,s,x,y,z;
while( scanf("%d%d%d",&n,&m,&s) != EOF ){
d.init(n);
for(int i = 0 ; i < m ; i++){
scanf("%d%d%d",&x,&y,&z);
d.AddEdge(y,x,z);
}
d.dijikstra(s);
scanf("%d",&m);
z = INF;
for(int i = 0; i < m ; i++){
scanf("%d",&x);
z = min(z,d.d[x]);
}
printf("%d\n",z == INF ? -1 : z);
}
return 0;
}