13 条题解
-
2
Nightingalelyy LV 10 @ 2017-04-06 22:14:05
#include <stdio.h> #include <algorithm> #include <queue> #include <cstring> #include <iostream> #include <string> #include <map> #include <ciso646> #include <stack> #include <cstdlib> using namespace std; const int maxn = 1000001; struct edge { int w; int v; int next; } g[maxn]; int n, m, i, j, ans; int tot=0; int head[maxn]; int dis[maxn]; bool inque[maxn]; void addedge(int u, int v, int w) { ++tot; g[tot].v = v; g[tot].w = w; g[tot].next = head[u]; head[u] = tot; return; } void spfa(int s) { queue<int> q; int u, i; q.push(s); dis[s] = 0; memset(inque, false, sizeof(inque)); inque[s] = true; while (!q.empty()) { u = q.front(); q.pop(); inque[u] = false; for (i = head[u];i != 0;i = g[i].next) { if (dis[g[i].v] > g[i].w + dis[u]) { dis[g[i].v] = g[i].w + dis[u]; if (!inque[g[i].v]) { q.push(g[i].v); inque[g[i].v] = true; } } } } return; } int main() { int n, m, k; scanf("%d%d%d", &n, &m, &k); for (i = 1;i <= n;i++) dis[i] = maxn; for (i = 1;i <= m;i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); addedge(u, v, w); addedge(v, u, w); } int cure[10000] = { 0 }; for (i = 1;i <= k;i++) { scanf("%d", &j); cure[j] = 1; } spfa(n); int ans = maxn; if (dis[1] == maxn) { printf("Oh no!\n"); return 0; } for (i = 1;i <= n;i++) if (cure[i]) ans = min(ans, dis[i]); printf("%d\n", ans); system("pause"); return 0; }刚好学了数组实现邻接表
赶紧来练一下。。。。。 -
1
//这道题我们发现走过一个治愈点后喋血值会归零，所以如何到这个点和答案一点关系都没有 //因此答案应该是从某一个治愈点到终点的最短路径，这里可以从终点反跑，同时特判不能到达终点的情况 //万一这个治愈点没法到达呢？ //既然可以从起点到终点，从终点到治愈点，那么就一定可以从起点到治愈点 //也就是说你可以在终点溜达一圈但是不进去（好怪） //于是只要一遍spfa就够了 #include<iostream> #include<vector> #include<cstring> using namespace std; vector<int> q[5010],p[5010]; int dui[200010],pan[5010],minn[5010],yao[5010]; int main() { memset(minn,0x3f,sizeof(minn)); int n,m,k,u,v,w,head,tail,d,now,ha,ans,i; cin>>n>>m>>k; for(i=1;i<=m;i++) { cin>>u>>v>>w; q[u].push_back(v); q[v].push_back(u); p[u].push_back(w); p[v].push_back(w); } for(i=1;i<=k;i++) cin>>yao[i]; minn[n]=0; pan[n]=1; head=1; tail=1; dui[1]=n; while(tail<=head) { ha=dui[tail]; d=q[ha].size(); for(i=0;i<d;i++) { now=q[ha][i]; if(minn[now]>minn[ha]+p[ha][i]) { minn[now]=minn[ha]+p[ha][i]; if(!pan[now]) { head++; dui[head]=now; pan[now]=1; } } } tail++; pan[ha]=0; } ans=minn[1]; for(i=1;i<=k;i++) ans=min(ans,minn[yao[i]]); if(minn[1]==0x3f3f3f3f) cout<<"Oh no!"; else cout<<ans; return 0; } -
1
裸地K+1遍SPFA竟然就能过，那就偷个懒
第一次判断连通性、
接下来枚举k个治愈点为起点求最短路
（记得初始化~）#include <iostream> #include <cstring> #include <cstdio> #include <queue> #define MAXM 50001 #define MAXN 5001 using namespace std; long n,heal[MAXN],idx,head[MAXN]; long dis[MAXN],m,k,dish[MAXN],ans=MAXM; bool vis[MAXN]; struct Node { long to,next,w; }edge[MAXM]; void init() { idx=1; memset(head,0,sizeof(head)); } void add(long u,long v,long w) { edge[idx].to=v; edge[idx].w=w; edge[idx].next=head[u]; head[u]=idx; idx++; } bool visit(int sta) { for(long i=1;i<=n;i++) { vis[i]=0; dis[i]=MAXM; } queue<long>Q; Q.push(sta); vis[sta]=1; dis[sta]=0; while(!Q.empty()) { long now=Q.front(); Q.pop(); vis[now]=0; for(long i=head[now];i;i=edge[i].next) { long w=edge[i].w; long son=edge[i].to; if(dis[now]+w<dis[son]) { dis[son]=dis[now]+w; if(!vis[son]) { Q.push(son); // 子节点未访问过 vis[son]=1; // 标记已访问 } } } } if (dis[n] == MAXM) return 0; else return 1; } int main() { cin>>n>>m>>k; for (long i=1;i<=m;i++) { long a,b,w; scanf("%d%d%d",&a,&b,&w); add(a,b,w); add(b,a,w); } for (long i=1;i<=k;i++) scanf("%d",&heal[i]); if ( !visit(1) ) { cout<<"Oh no!"<<endl; return 0; } for (long i=1;i<=k;i++) dish[i] = dis[heal[i]]; for (long i=1;i<=k;i++) { if (visit(heal[i])) ans = min( ans, dis[n]); } cout<<ans<<endl; return 0; } -
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 @ 2016-11-05 21:50:29
%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 @ 2015-07-13 19:27:50
orz
-
Nightingalelyy
LV 10
@ 2017-04-06 22:14:05
- 1
