1.裸题 hdu2544
http://acm.hdu.edu.cn/showproblem.php?pid=2544
Way1:
好像不对
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <stdbool.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
#define maxn 100+5
#define inf 1e9 long dist[maxn],road[maxn][maxn];
bool vis[maxn];
struct cmp
{
bool operator() (long a,long b)
{
return dist[a]>dist[b];
}
};
priority_queue<long,vector<long>,cmp> f; int main()
{
long n,m,i,j,x,y,z,d;
while ()
{
scanf("%ld%ld",&n,&m);
if (n== && m==)
break;
for (i=;i<=n;i++)
for (j=;j<=n;j++)
road[i][j]=inf;
for (i=;i<=m;i++)
{
scanf("%ld%ld%ld",&x,&y,&z);
road[x][y]=min(road[x][y],z);
road[y][x]=road[x][y];
}
for (i=;i<=n;i++)
{
vis[i]=false;
dist[i]=inf;
}
dist[]=;
//pay attention!
while (!f.empty())
f.pop();
f.push();
for (j=;j<n;j++) //use 'i' wrong!
{
while (vis[f.top()])
f.pop();
d=f.top();
if (d==n)
break;
vis[d]=true;
f.pop(); for (i=;i<=n;i++)
if (!vis[i] && dist[i]>dist[d]+road[i][d])
{
dist[i]=dist[d]+road[i][d];;
f.push(i);
}
}
printf("%ld\n",dist[n]);
}
return ;
}
/*
6 7
1 2 10
1 2 3
1 3 1
2 4 3
4 5 1
5 6 10
2 5 1
*/
Way2:
自行写堆，让堆中的值减小(路径长度减小)，在堆中上升。
只要掌握了合理的写法，其实也不是特别不好理解和难写
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <stdbool.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
#include <iostream>
using namespace std;
#define maxn 10000+5
#define inf 1e9 //pos[i]:编号为i的城市到起点的距离 在 树中的位置
long dist[maxn],road[maxn][maxn],tree[maxn],pos[maxn],g=;
bool vis[maxn]; //minimum-heap
void up(long i)
{
long j,temp;
while (i>)
{
j=i>>;
//i>j
if (dist[tree[i]]<dist[tree[j]])
{
temp=tree[i];
tree[i]=tree[j];
tree[j]=temp;
pos[tree[i]]=i;
pos[tree[j]]=j;
}
else
break;
i=j;
}
} void down(long i)
{
long j,temp;
while ((i<<)<=g)
{
j=i<<;
if (dist[tree[j+]]<dist[tree[j]])
j++;
//i<j
if (dist[tree[i]]>dist[tree[j]])
{
temp=tree[i];
tree[i]=tree[j];
tree[j]=temp;
pos[tree[i]]=i;
pos[tree[j]]=j;
}
else
break;
i=j;
}
} int main()
{
long n,m,i,j,x,y,z,d;
while ()
{
scanf("%ld%ld",&n,&m);
if (n== && m==)
break;
for (i=;i<=n;i++)
for (j=;j<=n;j++)
road[i][j]=inf;
for (i=;i<=m;i++)
{
scanf("%ld%ld%ld",&x,&y,&z);
road[x][y]=min(road[x][y],z);
road[y][x]=road[x][y];
}
for (i=;i<=n;i++)
{
vis[i]=false;
dist[i]=-;
}
dist[]=;
g=;
tree[]=;
pos[]=;
for (j=;j<n;j++) //use 'i' wrong!
{
d=tree[];
if (d==n)
break;
tree[]=tree[g];
pos[tree[]]=;
g--;
down(); vis[d]=true;
for (i=;i<=n;i++)
if (!vis[i])
{
if (dist[i]==-)
{
dist[i]=dist[d]+road[i][d];
g++;
tree[g]=i;
pos[i]=g;
up(g);
}
else if (dist[i]>dist[d]+road[i][d])
{
dist[i]=dist[d]+road[i][d];
up(pos[i]);
}
}
}
printf("%ld\n",dist[n]);
}
return ;
}
/*
6 7
1 2 10
1 2 3
1 3 1
2 4 3
4 5 1
5 6 10
2 5 1
*/
2.多关键字
L3-011. 直捣黄龙
https://www.patest.cn/contests/gplt/L3-011
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <stdbool.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
using namespace std;
#define maxn 200+5
#define inf 1e9 struct node
{
long kill,dist,free,count;
}point[maxn]; struct cmp
{
bool operator() (long a,long b)
{
return point[a].dist>point[b].dist;
}
};
priority_queue<long,vector<long>,cmp> f; long road[maxn][maxn],kill[maxn],pre[maxn],n;
char s[maxn][];
bool vis[maxn]; long find(char ss[])
{
long i;
for (i=;i<=n;i++)
if (strcmp(s[i],ss)==)
return i;
} void print(long d)
{
if (pre[d]!=-)
{
print(pre[d]);
printf("->%s",s[d]);
}
else
printf("%s",s[d]);
} int main()
{
char s1[],s2[];
long m,i,j,d,x,y,e;
scanf("%ld%ld%s%s",&n,&m,s1,s2);
for (i=;i<=n;i++)
{
point[i].dist=inf;
vis[i]=false;
}
for (i=;i<=n;i++)
for (j=;j<=n;j++)
road[i][j]=inf+;
point[n].kill=;
strcpy(s[n],s1);
pre[n]=-;
point[n].dist=;
point[n].free=;
point[n].count=;
f.push(n);
for (i=;i<n;i++)
{
scanf("%s%ld",s[i],&kill[i]);
if (strcmp(s2,s[i])==)
e=i;
}
for (i=;i<=m;i++)
{
scanf("%s%s%ld",s1,s2,&d);
x=find(s1);
y=find(s2);
road[x][y]=min(road[x][y],d);
road[y][x]=road[x][y];
}
for (j=;j<n;j++)
{
while (vis[f.top()])
f.pop();
d=f.top();
if (d==e)
break;
vis[d]=true;
for (i=;i<=n;i++)
if (!vis[i])
{
if (point[i].dist>point[d].dist+road[i][d])
{
pre[i]=d;
point[i].count=point[d].count;
point[i].dist=point[d].dist+road[i][d];
point[i].free=point[d].free+;
point[i].kill=point[d].kill+kill[i];
f.push(i);
}
else if (point[i].dist==point[d].dist+road[i][d])
{
point[i].count+=point[d].count;
if ((point[i].free<point[d].free+) ||
(point[i].free==point[d].free+ && point[i].kill<point[d].kill+kill[i]))
{
pre[i]=d;
point[i].free=point[d].free+;
point[i].kill=point[d].kill+kill[i];
f.push(i);
}
}
}
}
print(e);
printf("\n%ld %ld %ld\n",point[e].count,point[e].dist,point[e].kill);
return ;
}