13 条题解
-
2
Nightingalelyy LV 10 @ 8 年前
刚好学了数组实现邻接表
赶紧来练一下。。。。。 -
0
#include <cstdio>
#include <queue>
#define INF 99999999struct edge{
int v,val;
edge *link;
};int n,m,cure[5100]={0},top=0;
edge graph[5100]={0};
edge node[51000];void add(int u,int v,int val){
edge *l=&node[top++];
l->v=v,l->val=val;
l->link=graph[u].link;
graph[u].link=l;
}void build(){
int k,x;
scanf("%d%d%d",&n,&m,&k);
int u,v,val;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&val);
add(u,v,val);
add(v,u,val);
}
for(int i=1;i<=k;i++){
scanf("%d",&x);
cure[x]=1;
}
}
//SPFA
std::queue<int> q;
int dist[5100],inque[5100]={0};void spfa(int u){
dist[u]=0;
q.push(u),inque[u]=1;
while(!q.empty()){
int t=q.front();
q.pop(),inque[t]=1;
edge *l=graph[t].link;
while(l){
if(dist[l->v]>dist[t]+l->val){
dist[l->v]=dist[t]+l->val;
if(!inque[l->v]){
q.push(l->v);
inque[l->v]=1;
}
}
l=l->link;
}
}
}int main(){
freopen("in.txt","r",stdin);
build();
for(int i=1;i<=n;i++)
dist[i]=INF;
spfa(n);
if(dist[1]==INF){
printf("Oh no!");
return 0;
}
int ans=INF;
for(int i=1;i<=n;i++)
if(cure[i])
ans=ans<dist[i]?ans:dist[i];
printf("%d",ans);
return 0;
} -
0
仅需一遍SPFA：我看你们都没有人点出重点，我这个蒟蒻就说了吧：
以终点作为最短路起点SPFA，分别判断起点和治愈点的举例即可，仅需一遍SPFA！一遍SPFA！一遍SPFA！
cpp
#define Rep(i,n) for(int i=1;i<=n;i++)
#define pINF 100000
#include<cstdio>
#include<memory.h>
#include<queue>
using namespace std;
long Edge[5001][5001];
long n,m,k;
long d[5001];
bool inqueue[5001];
long k_arr[5001];
queue<long> q;
long spfa(long start){
while(!q.empty())q.pop();
memset(d,0x7F,sizeof(long)*5001);
memset(inqueue,false,sizeof(bool)*5001);
q.push(start);
d[start]=0;
inqueue[start]=true;
while(!q.empty()){
int node=q.front();
q.pop();
inqueue[node]=false;
Rep(i,n){
if(Edge[node][i]!=-1){//有边
if(d[i]>d[node]+Edge[node][i]){
d[i]=d[node]+Edge[node][i];
if(!inqueue[i]){
q.push(i);
inqueue[i]=true;
}
}
}
}
}
if(d[1]>pINF)return d[1];
else {
long min=pINF;
Rep(i,k){
if(d[k_arr[i]]<min)min=d[k_arr[i]];
}
return min;
}
}
int main(){
scanf("%ld%ld%ld",&n,&m,&k);
memset(Edge,-1,sizeof(long)*5001*5001);
Rep(i,m){
long x,y,z;
scanf("%ld%ld%ld",&x,&y,&z);
if(Edge[x][y]==-1||Edge[x][y]>z){
Edge[x][y]=z;
Edge[y][x]=z;
}
}
Rep(i,k){
scanf("%ld",&k_arr[i]);
}
long spfa_result=spfa(n);
if(spfa_result>=pINF){
printf("Oh no!");
return 0;
}else{
printf("%ld",spfa_result);
}
}
-
0
需要两遍SPFA？判断连通性只需从终点跑一边SPFA
#include <cstdio>
#include <queue>
#include <iostream>struct edge{
int v,val;
edge *link;
}graph[5100]={0},node[50100];int n,m,k,top=0,cure[5100]={0};
void AddEdge(int u,int v,int val){
edge *l=&node[top++];
l->v=v,l->val=val;
l->link=graph[u].link;
graph[u].link=l;
}void BuildGraph(){
scanf("%d%d%d",&n,&m,&k);
int u,v,val,t;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&val);
AddEdge(u,v,val);
AddEdge(v,u,val);
}
for(int i=1;i<=k;i++){
scanf("%d",&t);
cure[t]=1;
}
}//SPFA
std::queue<int> q;
int inque[5100]={0};
int dist[5100];void spfa(int u){
for(int i=1;i<=n;i++)
dist[i]=99999999;
dist[u]=0;
q.push(u),inque[u]=1;
int t;
edge *l;
while(!q.empty()){
t=q.front();
q.pop(),inque[t]=0;
l=graph[t].link;
while(l){
if(dist[l->v]>dist[t]+l->val){
dist[l->v]=dist[t]+l->val;
if(!inque[l->v]){
q.push(l->v);
inque[l->v]=1;
}
}
l=l->link;
}
}
}int main(){
freopen("in.txt","r",stdin);
BuildGraph();
spfa(n);
if(dist[1]==99999999){
printf("Oh no!");
return 0;
}
int ans=dist[1];
for(int i=1;i<=n;i++)
if(cure[i]==1)
ans=ans<dist[i]?ans:dist[i];
printf("%d",ans);
return 0;
} -
0
编译成功
foo.cpp:10:23: warning: integer overflow in expression [-Woverflow]
const int INF=(2<<30)-1;
^
测试数据 #0: Accepted, time = 0 ms, mem = 1272 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1272 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1268 KiB, score = 10
测试数据 #3: Accepted, time = 15 ms, mem = 1276 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1268 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 1272 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 1268 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 1272 KiB, score = 10
测试数据 #8: Accepted, time = 15 ms, mem = 1280 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 1276 KiB, score = 10
Accepted, time = 60 ms, mem = 1280 KiB, score = 100一遍SPFA就够了为啥要k+1？
-
0
考虑对于每个cure点都是起点，跑最短路
找最小的
记得以1点为起点跑一遍spfa判连通性
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
#define MAX 5100
#define Max 999999999
struct Edge {
int to;
int c;
};
int Ans = Max;
int n, mm, k;
int start[MAX];
vector<Edge> m[MAX];
int SPFA(int Start) {
int dis[MAX];
bool b[MAX];
for (int i = 1; i <= n; i++) {
dis[i] = Max;
b[i] = false;
}
queue<int> t;
dis[Start] = 0;
b[Start] = true;
t.push(Start);
while (!t.empty()) {
int p = t.front();
t.pop();
b[p] = false;
for (size_t i = 0; i < m[p].size(); i++) {
int to = m[p][i].to;
if (dis[to] > dis[p] + m[p][i].c) {
dis[to] = dis[p] + m[p][i].c;
if (!b[to]) {
b[to] = true;
t.push(to);
}
}
}
}
return dis[n];
}
int read() {
int x = 0;
int f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
return x*f;
}
void Initalize() {
n = read();
mm = read();
k = read();
for (int i = 1; i <= mm; i++) {
int u = read();
int v = read();
int c = read();
Edge edge;
edge.to = u;
edge.c = c;
m[v].push_back(edge);
edge.to = v;
m[u].push_back(edge);
}
for (int i = 1; i <= k; i++)
start[i] = read();
}
int main() {
Initalize();
for (int i = 1; i <= k; i++)
Ans = min(Ans, SPFA(start[i]));
Ans = min(Ans, SPFA(1));
if (Ans == Max) {
cout << "Oh no!" << endl;
}
else cout << Ans << endl;
}另楼下傻逼hory
-
0
#include <iostream>
#include <stdio.h>
#include <queue>
#include <vector>using namespace std;
int n , m , k;
int i , j;
int dist[5000 + 2];
int use[5000 + 2];
vector < int > g[5000 + 2];
vector < int > v[5000 + 2];
queue < int > q;
int p;
int mind;
int x , y , w;int min( int a , int b )
{
if( a > b )
return b;
return a;
}void spfa()
{
q.push( n );
dist[n] = 0;
int now;
int i;
while( !q.empty() )
{
now = q.front();
q.pop();
use[ now ] = 0;
for( i = 0 ; i < g[now].size() ; i++ )
if( dist[ g[now][i] ] > dist[now] + v[now][i] )
{
dist[ g[now][i] ] = dist[now] + v[now][i];
if( !use[ g[now][i] ] )
{
q.push( g[now][i] );
use[ g[now][i] ] = 1;
}
}
}
return;
}int main()
{
scanf( "%d %d %d" , &n , &m , &k );
for( i = 1 ; i <= n ; i++ )
dist[i] = 100000000;
for( i = 0 ; i < m ; i++ )
{
scanf( "%d %d %d" , &x , &y , &w );
g[x].push_back( y );
v[x].push_back( w );
g[y].push_back( x );
v[y].push_back( w );
}
spfa();
mind = 100000000;
for( i = 0 ; i < k ; i++ )
{
scanf( "%d" , &p );
mind = min( mind , dist[p] );
}
mind = min( mind , dist[1] );
if( mind == 100000000 )
cout << "Oh no!" << endl;
else
cout << mind << endl;
return 0;
}
为什么输出ohno。。。-
sslz_zht @ 8 年前
%LXL
-
-
0
咯……好多人第一次都被这题坑道了……我这个小水渣就来充当一下大神发发题解吧。
其实这题可以往回走的，你可以走道一个治愈点去恢复，然后在继续出发到终点哦！！！
大概的算法是搜索所有从1可以到达的点，如果n是不可到达的，直接输出Oh no！结束程序。
从治愈点出发到终点 和从起点出发到终点有什么区别呢？答案是：没有！我们用最后一个点为源点向前寻找到其他点的最短路。我用的是DJ算法，dis数组记录第i个点到n的距离。从所有能够到达的治愈点里面找到离终点最近的那个就可以啦。。。
本人小新手，如果大神有什么其他的意见可以提出来哦，以下是代码，如果想直接copy交上去也可以，是可以直接AC哒。
program a01; {if i were DJ}
var
f:array[1..10002,1..10002] of longint;
cure,dis:array[1..10002] of longint;
visit,s:array[1..10002] of boolean;
r,q,m,ans,mark,point,n,k,i,j:longint;procedure dfs(l:longint);
var
i:longint;
begin
visit[l]:=true;
for i :=1 to n do
if (f[l,i]< maxint) and(not visit[i]) then dfs(i);
end;begin
ans:=maxlongint;
read(n,m,r);
s[n]:=true;for i := 1 to n do
for j := 1 to n do
f[i,j]:= maxint;for q := 1 to m do
begin
read(i,j);
read(f[i,j]);
f[j,i]:=f[i,j];
end;for i := 1 to r do
read(cure[i]); {read}dfs(1);
if not visit[n] then begin
writeln('Oh no!');
halt;
end;for i := 1 to n do {DJ}
dis[i]:=f[i,n];
for k := 1 to n-2 do
begin
mark:=maxlongint;
for i := 1 to n-1 do
if not (s[i]) and (mark>dis[i]) then begin
mark:=dis[i];
point:=i;
end;
s[point]:=true;
for i := 1 to n-1 do
if dis[point]+f[point,i]<dis[i] then begin
dis[i]:=dis[point]+f[point,i];
end;
end; {DJ over on here}for i := 1 to r do
if dis[cure[i]]<ans then ans:=dis[cure[i]];
if dis[1]<ans then ans:=dis[1];
writeln(ans);
end.-
yingjiangyu @ 9 年前
orz
-
Nightingalelyy
LV 10
@ 8 年前
- 1
