继第一篇的后续，又来刷水题了，写的是SPFA算法，这个算法的复杂度比较玄学，感觉能不用就不用了，但是他的好处就是可以判断负圈。
3月26日：
1.POJ 1847 Tram
题意：在一个交通网络上有N个路口, 每个路口指向多个方向, 默认驶向第一个方向, 驶向其他方向时需要进行一次操作, 求从a到b最小的操作数
直接建图即可，默认的方向权值为0，其他方向权值为1。
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 110
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int n,st,en;
int visited[maxn];
struct wazxy{
int v,next,w;
}edge[maxn*maxn];
int head[maxn];
int dis[maxn];
int cnt=0;
void init(){
memset(visited,false,sizeof(visited));
memset(dis,MaxN,sizeof(dis));
memset(head,-1,sizeof(head));
}
void add(int u,int v,int w){
edge[cnt].w=w;
edge[cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void spfa(){
queue<int> q;
q.push(st);
dis[st]=0;
while(!q.empty()){
int temp=q.front();
q.pop();
visited[temp]=false;
for(int i=head[temp];~i;i=edge[i].next){
int v=edge[i].v;
int w=dis[temp]+edge[i].w;
if(dis[v]>w){
dis[v]=w;
if(!visited[v]){
visited[v]=true;
q.push(v);
}
}
}
}
}
int main()
{
cin>>n>>st>>en;
init();
for(int i=1;i<=n;i++){
int m,x;
scanf("%d",&m);
bool flag=true;
for(int f=1;f<=m;f++){
scanf("%d",&x);
if(flag) add(i,x,0),flag=false;
else add(i,x,1);
// cout<<i<<" "<<x<<endl;
}
}
spfa();
// for(int i=1;i<=n;i++) cout<<dis[i]<<endl;
if(dis[en]!=MaxN) printf("%d\n",dis[en]);
else printf("-1\n");
return 0;
}
2.POJ 2502 Subway
首先，原谅我这个题做了一晚上，找了一个多小时的bug，当ac此题时，原谅我仰天长啸3s，出错原因竟然是极大值附小了，我他妈！！！！！！淦
题意：个人要从家到学校，步行速度10km/h，图上有地铁40km/h，地铁有不同线路，每个线路上的地铁可以互通，相邻两站之间地铁以直线运行，不同地铁线路之间不能直接通过地铁乘坐到达，但不同地点间可以直接步行，按直线走。给出家、学校、各地铁站台的坐标（单位 m），问从家到学校最短需要花费多少时间（min），不要忘记换算单位。
思路：先把每条铁路建成图（速度为车速），再把每个站点之间连起来（相当于人走）。
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 100010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
const int mod = 1e9 + 7;
using namespace std;
int sx,sy,ex,ey;
int n;
bool visited[maxn];
struct wazxy{
int v,next;
double w;
}edge[maxn];
struct point{
int x,y;
}a[maxn];
int head[maxn];
long double dis[maxn];
int cnt=0;
int num=1;
void init(){
memset(visited,false,sizeof(visited));
for(int i=0;i<maxn;i++) dis[i]=1e18;
memset(head,-1,sizeof(head));
}
void add(int u,int v,double w){
edge[cnt].w=w;
edge[cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void spfa(){
queue<int> q;
q.push(0);
dis[0]=0;
while(!q.empty()){
int temp=q.front();
q.pop();
visited[temp]=false;
for(int i=head[temp];~i;i=edge[i].next){
int v=edge[i].v;
double w=dis[temp]+edge[i].w;
if(dis[v]>w){
dis[v]=w;
if(!visited[v]){
visited[v]=true;
q.push(v);
}
}
}
}
}
inline double getlen(double x,double y,double x1,double y1,double s){
return 60*sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1))/s/1000;
}
int main()
{
cin>>sx>>sy>>ex>>ey;
int x,y,x1,y1;
a[0].x=sx,a[0].y=sy;
init();
while(scanf("%d%d",&x,&y)!=EOF){
a[num].x=x,a[num++].y=y;
while(scanf("%d%d",&x1,&y1)!=EOF&&x1!=-1){
a[num].x=x1,a[num++].y=y1;
double temp=getlen(x,y,x1,y1,40);
// cout<<temp<<endl;
add(num-2,num-1,temp);
add(num-1,num-2,temp);
x=x1,y=y1;
}
}
a[num].x=ex,a[num++].y=ey;
for(int i=0;i<num;i++){
for(int j=0;j<num;j++){
if(i==j) continue;
double temp=getlen(a[i].x,a[i].y,a[j].x,a[j].y,10);
// cout<<temp<<endl;
add(i,j,temp);
}
}
num--;
spfa();
//for(int i=0;i<=num;i++) cout<<dis[i]<<endl;
printf("%d\n",(int)(dis[num]+0.5));
return 0;
}
3.POJ 1062 昂贵的聘礼
这个题只需要额外的一个附加条件，就是在某段区间内进行查询最短，在spfa种设置一个范围即可。
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 1010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
ll mod = 998244353;
using namespace std;
struct wazxy{
int v,w,next;
}edge[100010];
bool visited[maxn];
int dis[maxn];
int lv[maxn];
int cnt=0;
int head[maxn];
int n,m;
void add(int u,int v,int w){
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
int spfa(int l,int r){
memset(visited,false,sizeof(visited));
memset(dis,MaxN,sizeof(dis));
queue<int> q;
dis[0]=0;
q.push(0);
while(!q.empty()){
int temp=q.front();
q.pop();
visited[temp]=false;
for(int i=head[temp];~i;i=edge[i].next){
int v=edge[i].v;
if(!(lv[v]>=l&&lv[v]<=r)) continue;
int w=dis[temp]+edge[i].w;
if(dis[v]>w){
dis[v]=w;
if(!visited[v]){
visited[v]=false;
q.push(v);
}
}
}
}
return dis[1];
}
int main()
{
memset(head,-1,sizeof(head));
cin>>m>>n;
for(int i=1;i<=n;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
add(0,i,x);
lv[i]=y;
while(z--){
int v,w;
scanf("%d%d",&v,&w);
add(v,i,w);
}
}
int imin=MaxN;
for(int i=lv[1]-m;i<=lv[1];i++){
imin=min(imin,spfa(i,i+m));
}
cout<<imin<<endl;
return 0;
}
3月30
4.poj1860 Currency Exchange floyd
出去爬了个泰山，还是比较累的，继续鏖战最短路
思路：这个题目利用了spfa判断正环，这个做法是最保险的，因为如果存在正环的话金钱就会一直增加。
代码：
#pragma GCC optimize(3,"Ofast","inline")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <math.h>
#include <string>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#define maxn 1010
//#define true false
//#define false true
const int MaxN = 0x3f3f3f3f;
const int MinN = 0xc0c0c00c;
const double pi = acos(-1);
typedef long long ll;
ll mod = 998244353;
using namespace std;
int visited[maxn];
double dis[maxn];
int n,m,s;
double v;
int head[maxn];
struct wazxy{
double w;
int next;
double rate;
int v;
}edge[1010];
int cnt=0;
int ans[maxn];
void add(int u,int v,double r,double w){
edge[cnt].rate=r;
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
}
bool spfa(){
queue<int> q;
q.push(s);
visited[s]=true;
dis[s]=v;
ans[s]++;
while(!q.empty()){
int temp=q.front();
q.pop();
visited[temp]=false;
for(int i=head[temp];~i;i=edge[i].next){
int to=edge[i].v;
double r=edge[i].rate;
double w=edge[i].w;
if(dis[to]<(dis[temp]-w)*r){
dis[to]=(dis[temp]-w)*r;
if(!visited[to]){
visited[to]=true;
ans[to]++;
q.push(to);
}
if(ans[to]>n) return true;
}
}
}
return false;
}
int main()
{
cin>>n>>m>>s>>v;
memset(visited,false,sizeof(visited));
memset(head,-1,sizeof(head));
for(int i=0;i<maxn;i++) dis[i]=0;
for(int i=1;i<=m;i++){
int x,y;
double a,b;
cin>>x>>y>>a>>b;
add(x,y,a,b);
cin>>a>>b;
add(y,x,a,b);
}
if(spfa()) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
return 0;
}
昨晚本来想写，遗憾的是女朋友被猫咬了，陪她去医院***没写成；；
算了就写这些吧
京公网安备 11010502036488号