图论--（最短路，最小生成树）的一些水题
最近写kuangbin专题，记录一下吧。
目录
POJ-1511-Invitation Cards（建两次图，裸Dijkstr）
POJ-1847-Tram（读完题之后，裸Dijkstra，水题）
LightOJ-1074-Extended Traffic(SPFA-负环）
POJ-1511-Invitation Cards（建两次图，裸Dijkstr）
题目链接：http://poj.org/problem?id=1511
题目大意：1~n个点，n个人，然后给你一个有向图，问所有人从1出发，每要求每个点都有一个人，然后人们再回到1点，问最小花费是多少，
思路：之前似乎做过类似的，正向建一次，Dijkstr，反向建一次，Dijkstr，输出ans，注意这里提上说的是输入的数是int，不排除计算的时候可能到ll，所以变量用ll
AC：woc！突然发现我这个代码使用优先队列的时候没有确定优先级？？这都能过？？算了，当作没看见吧，下次注意一点
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
//#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define Pair pair<int,ll>
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// ??
//std::ios::sync_with_stdio(false);
const int MAXN=1e6+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
const double PI=acos(-1.0);
struct node{
ll v,val,nxt;
node(ll _v=0,ll _val=0,ll _nxt=0){
v=_v;val=_val;nxt=_nxt;
}
}edge[MAXN<<1];
int head[MAXN],ecnt;
ll a[MAXN],b[MAXN],val[MAXN];
ll dis[MAXN];
int n,m;
void intt(){
clean(head,-1);
ecnt=0;
}
void add(ll u,ll v,ll val){
edge[ecnt]=node(v,val,head[u]);
head[u]=ecnt++;
}
void Dijkstr(){
clean(dis,INF64);dis[1]=0;
priority_queue<Pair> que;while(que.size()) que.pop();
que.push({1,0});
while(que.size()){
Pair e=que.top();que.pop();
//printf(" %d_%d ",e.first,e.second);
// vis[e.first]=1;
for(int i=head[e.first];i+1;i=edge[i].nxt){
int temp=edge[i].v;
if(dis[temp]>dis[e.first]+edge[i].val){
dis[temp]=dis[e.first]+edge[i].val;
que.push({temp,dis[temp]});
}
}
}
}
int main(){
int T;scanf("%d",&T);
while(T--){
intt();
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%lld%lld%lld",&a[i],&b[i],&val[i]);
add(a[i],b[i],val[i]);
}Dijkstr();ll ans=0;
for(int i=1;i<=n;++i){
ans+=dis[i];//printf("%d_:_%d ",i,dis[i]);
}intt();//printf("\n");
for(int i=1;i<=m;++i){
add(b[i],a[i],val[i]);
}Dijkstr();
for(int i=1;i<=n;++i){
ans+=dis[i];//printf("%d_:_%d ",i,dis[i]);
}printf("%lld\n",ans);
}
}
/*
*/ POJ-2502-Subway(最短路）
题目链接：http://poj.org/problem?id=2502
题目大意：给出起点和终点，输入一些地铁的站点，每条地铁线以(-1,-1)结尾。人能选择走路||坐地铁，速度分别为：10Km/h和40Km/h；问从起点到终点所用的最短时间。
思路：建图麻烦，但是建好图之后就是裸的Dijkstra了。
ACCode：
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
//#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define Pair pair<int,int>
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// 水印
//std::ios::sync_with_stdio(false);
// register
const int MAXN=2e2+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
const double PI=acos(-1.0);
struct Point{
double x,y;int Line;
Point(double _x=-1,double _y=-1,int _Line=-1){
x=_x;y=_y;Line=_Line;
}
}s,t,Dots[MAXN];
double Dis[MAXN],Mp[MAXN][MAXN];
int Vis[MAXN];
int n,m;
void Debug(){
for(int i=0;i<=n;++i){
printf("(%lf,%lf,%d) - ",Dots[i].x,Dots[i].y,Dots[i].Line);
}printf("\n");
for(int i=0;i<=n;++i){
for(int j=0;j<=n;++j){
printf("%18lf ",Mp[i][j]);
}printf("\n");
}printf("\n");
}
void intt(){
for(int i=0;i<MAXN;++i){
for(int j=0;j<MAXN;++j){
Mp[i][j]=999999999;
}Dis[i]=999999999;Vis[i]=0;
}
}
void Dijkstra(){
Dis[0]=0;
for(int i=0;i<=n;++i){
int can=-1;double minn=999999999;
for(int j=0;j<=n;++j){
if(Vis[j]==0&&Dis[j]<minn){
can=j;minn=Dis[j];
}
}Vis[can]=1;
for(int j=0;j<=n;++j){
if(Vis[j]==0&&Dis[j]>Mp[can][j]+Dis[can]){
Dis[j]=Mp[can][j]+Dis[can];
}
}
}
}
int main(){
intt();
scanf("%lf%lf%lf%lf",&s.x,&s.y,&t.x,&t.y);
Dots[0]=Point(s.x,s.y,0);
Point a,b;int ecnt=1,kind=1;
while(~scanf("%lf%lf",&a.x,&a.y)){
if(a.x==-1&&a.y==-1){
kind++;
}
else Dots[ecnt++]=Point(a.x,a.y,kind);
}n=ecnt;Dots[n]=Point(t.x,t.y,kind);
for(int i=0;i<=n;++i){
for(int j=0;j<=n;++j){
if(Dots[i].Line==Dots[j].Line&&abs(i-j)==1){
double dis=sqrt((Dots[i].x-Dots[j].x)*(Dots[i].x-Dots[j].x)+(Dots[i].y-Dots[j].y)*(Dots[i].y-Dots[j].y));
Mp[i][j]=Mp[j][i]=(dis*3.0)/2000.0;
}
else{
double dis=sqrt((Dots[i].x-Dots[j].x)*(Dots[i].x-Dots[j].x)+(Dots[i].y-Dots[j].y)*(Dots[i].y-Dots[j].y));
Mp[i][j]=Mp[j][i]=(dis*6.0)/1000.0;
}
}
}//Debug();
Dijkstra();
printf("%.0f\n",Dis[n]);
} POJ-1062-昂贵的聘礼（枚举最短路，n次）
题目链接：http://poj.org/problem?id=1062
题目大意：中文题，读题就好。
思路：这道题好迷啊，题上说的地位限制是交换序列中的所有人之间的地位相差不能超过m，跑了n次Dijkstra才AC，之前一直只跑一遍，都快写成BFS了….WA了一页（大哭..
ACCode：
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define Pair pair<int,int>//,pair<int,int> >
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// 水印
//std::ios::sync_with_stdio(false);
// register
const int MAXN=3e2+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
const double PI=acos(-1.0);
int Mp[MAXN][MAXN];
int Dis[MAXN],Vis[MAXN],Status[MAXN];
int n,m,str,ed;
struct Cmp{
bool operator ()(const Pair &a,const Pair &b){
return a.second>b.second;
}
};
void Dijkstra(int minn){
if(minn+m<Status[1]) return ;
clean(Dis,INF32);Dis[str]=0;
clean(Vis,0);
priority_queue<Pair,vector<Pair>,Cmp> que;
que.push(make_pair(str,0));
//que.push({str,{0,INF32}});
int ans=INF32;
while(que.size()){
Pair u=que.top();que.pop();
// cout<<u.first<<" "<<u.second<<" "<<minn<<" -> ";
if(Vis[u.first]) continue;
Vis[u.first]=1;
for(int i=1;i<=n;++i){
if(Vis[i]==0&&Dis[i]>Mp[u.first][i]+Dis[u.first]
&&Status[i]<=minn+m&&Status[i]>=minn){
Dis[i]=Mp[u.first][i]+Dis[u.first];
que.push(make_pair(i,Dis[i]));
}
}//cout<<endl;
}
}
int main(){
clean(Mp,INF32);str=210;ed=1;
clean(Vis,0);
scanf("%d%d",&m,&n);
int val,status,T,a,b;
for(int i=1;i<=n;++i){
scanf("%d%d%d",&val,&status,&T);
Mp[str][i]=val;Status[i]=status;
for(int j=1;j<=T;++j){
scanf("%d%d",&a,&val);
Mp[a][i]=val;
}
}int ans=INF32;
for(int i=1;i<=n;++i){
Dijkstra(Status[i]);
// for(int i=1;i<=n;++i){
// cout<<Dis[i]<<" ";
// }cout<<endl;
ans=min(ans,Dis[1]);
}printf("%d\n",ans);
}
/*
*/
POJ-1847-Tram（读完题之后，裸Dijkstra，水题）
题目链接：http://poj.org/problem?id=1847
题目大意：给出n个路口，每个路口能到其他K个路口，能到的第一个路口为默认方向。问从s到t最少变换几次方向。
思路：存图存成有向图，然后直接一个Dijkstra即可。
ACCode：
// luogu-judger-enable-o2
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdlib.h>
#include<string.h>
#include<stdio.h>
#include<math.h>
#include<time.h>
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define Pair pair<int,int>
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// 水印
//std::ios::sync_with_stdio(false);
// register
const int MAXN=2e2+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const int MOD=998244353;
const double EPS=1.0e-12;
const double PI=acos(-1.0);
int Mp[MAXN][MAXN];
int Dis[MAXN],Vis[MAXN];
int n;
struct Cmp{
bool operator ()(const Pair &a,const Pair &b){
return a.second>b.second;
}
};
void Dijkstra(int op,int ed){
clean(Dis,INF32);Dis[op]=0;
clean(Vis,0);
priority_queue<Pair,vector<Pair>,Cmp> que;que.push({op,0});
while(que.size()){
Pair u=que.top();que.pop();
if(Vis[u.first]) continue;
Vis[u.first]=1;
for(int i=1;i<=n;++i){
if(Vis[i]==0&&Dis[i]>Dis[u.first]+Mp[u.first][i]){
Dis[i]=Dis[u.first]+Mp[u.first][i];
que.push({i,Dis[i]});
}
}
}
}
int main(){
clean(Mp,INF32);
int op,ed;scanf("%d%d%d",&n,&op,&ed);
int k,target;
for(int i=1;i<=n;++i){
scanf("%d",&k);
for(int j=1;j<=k;++j){
scanf("%d",&target);
if(j==1) Mp[i][target]=0;
else Mp[i][target]=1;
}
}Dijkstra(op,ed);
printf("%d\n",Dis[ed]==INF32?-1:Dis[ed]);
}
/*
*/
LightOJ-1074-Extended Traffic(SPFA-负环）
题目链接：http://lightoj.com/login_main.php?url=volume_showproblem.php?problem=1074
题目大意：给出每个城市的拥堵程度，m条单向路，每条道路的权值就是(end-start)^3。然后q次查询，每次找出1到dest的最小的权值的道路，如果这个城市没法到达||权值之和<3那么就输出"?"否则输出权值。
思路：简单的一道最短路，可能存在负环，所以SPFA判断，存在负环的话，周围所有能够连接到的点都可以是-INF，所以以负环点为中心再次DFS标记能直接相连的点。最后输出的时候判断一下是否在负环中即可。（一开始数组存图，挂了，调不出来，后来向前星存图，nxt和val写反了，找了半天bug..TAT）
ACCode：
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
#define Pair pair<int,ll>
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))
//std::ios::sync_with_stdio(false);
// register
const int MAXN=2e2+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const ll mod=1e9+7;
const double EPS=1.0e-8;
const double PI=acos(-1.0);
struct node{
int v,nxt;ll w;
node(int _v=0,int _w=0,ll _nxt=0){
v=_v;w=_w;nxt=_nxt;
}
}Edge[MAXN*MAXN];
int head[MAXN],ecnt;
ll Busyness[MAXN];
ll Dis[MAXN],Sum[MAXN];
int Vis[MAXN],Cir[MAXN];
int Stk[MAXN*MAXN],Top;
int n,Flag;
void Add(int u,int v,ll w){
Edge[ecnt]=node(v,w*w*w,head[u]);
head[u]=ecnt++;
}
void DFS(int u){
Cir[u]=1;
for(int i=head[u];i+1;i=Edge[i].nxt){
if(Cir[Edge[i].v]==0){
DFS(Edge[i].v);
}
}
}
void DFS_SPFA(){
clean(Dis,INF64);Dis[1]=0;
clean(Vis,0);Vis[1]=1;
clean(Sum,0);Sum[1]=1;
clean(Cir,0);
Top=0;Stk[Top++]=1;
while(Top){
int u=Stk[--Top];Vis[u]=0;
if(Sum[u]>n||Cir[u]==1) continue;
for(int i=head[u];i+1;i=Edge[i].nxt){
int temp=Edge[i].v;//cout<<"temp:"<<temp<<endl;
if(Dis[temp]>Dis[u]+Edge[i].w){
Dis[temp]=Dis[u]+Edge[i].w;
if(Vis[temp]==0){
Vis[temp]=1;Sum[temp]++;
Stk[Top++]=temp;
if(Sum[temp]>n){
DFS(temp);
}
}
}
}
}
}
void Debug(){
// for(int i=1;i<=n;++i) cout<<"head i："<<head[i]<<endl;
for(int i=1;i<=n;++i){
cout<<i<<": ";
for(int j=head[i];j+1;j=Edge[j].nxt){
cout<<Edge[j].v<<" ";
}cout<<endl;
}
}
int main(){
int Case=1,T;scanf("%d",&T);
while(T--){
clean(head,-1);ecnt=0;
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%lld",&Busyness[i]);
}int m,a,b;scanf("%d",&m);
// for(int i=1;i<=n;++i) cout<<"head i:"<<head[i]<<endl;
for(int i=1;i<=m;++i){
scanf("%d%d",&a,&b);
Add(a,b,Busyness[b]-Busyness[a]);
//Mp[a][b]=(Busyness[b]-Busyness[a])*(Busyness[b]-Busyness[a])*(Busyness[b]-Busyness[a]);
}//Debug();
int Q;scanf("%d",&Q);DFS_SPFA();
printf("Case %d:\n",Case++);int dest;
while(Q--){
scanf("%d",&dest);
if(Dis[dest]==INF64||Dis[dest]<3||Cir[dest]) printf("?\n");
else printf("%lld\n",Dis[dest]);
}
}
}
学而思开奖43人在聊
