C++14(g++5.4) 解法, 执行用时: 33ms, 内存消耗: 27572K, 提交时间: 2020-10-05 17:40:17

#include <bits/stdc++.h>
using namespace std;
#define sc scanf
#define pr printf
#define ll long long int
#define mst(x) memset(x, 0 ,sizeof x)
#define FILE_OUT freopen("out", "w", stdout);
#define FILE_IN freopen("in", "r", stdin);
#define debug(a,b) cout<<a<<" : "<<b<<endl;
#define INF 0x3f3f3f3f3f3f 
#define Int register int
const ll MAX_N = 4e6+5;
const ll mod = 1e9+7;
int N, M, K;

int tot;
int head[MAX_N];
struct Edge{
	int to, nxt;
	double w;
}edge[MAX_N];


void addEdge(int u, int v, double w){
	edge[tot].nxt = head[u];
	edge[tot].to = v;
	edge[tot].w = w;
	head[u] = tot++;
//	edge[tot].nxt = head[v];
//	edge[tot].to = u;
//	edge[tot].w = w;
//	head[v] = tot++;
}

typedef pair<double, int>P;
double dis[MAX_N];
bool vis[MAX_N];
priority_queue<P, vector<P>, greater<P>>Q;
void Dijkstra(int id){
	while (Q.size()) Q.pop();
	dis[id] = 0;
	Q.push({0, id});
	int u, v;
	double w;
	while (Q.size()){
		P t = Q.top();Q.pop();
//		if (dis[u=t.second] < t.first)continue;
		if (vis[u=t.second])continue;
//		debug("u",u);
		vis[u] = 1;
		for (Int i = head[u];~i;i=edge[i].nxt){
			if (dis[v=edge[i].to] <= dis[u] + (w=edge[i].w))continue;
			dis[v] = dis[u] + w;
			Q.push({dis[v], v});
		}
	}
}


void init(){
	tot = 0;
	memset(head, -1, sizeof head);
	memset(vis, 0, sizeof vis);
	for (Int i = 1; i <= N*(K+2); ++i){
		dis[i] = INF;
	}
}

void solve(){
	sc("%d%d", &N, &K);
	init();
	int u, v, w;
	for (int i = 1; i <= N; ++i){
		for (int j = 1; j <= N; ++j){
			sc("%1d", &w);
//			if (!w)continue;
			for (Int k = 0; k <= K; ++k){
				//cout<<"u "<<i+N*k<< " v: "<<j + N*k<<endl;
				//cout<<"u "<<j+N*k<< " v: "<<i + N*k<<endl;
				addEdge(i+N*k, j+N*k, w*1.0);
				addEdge(j+N*k, i+N*k, w*1.0);
				if (k<K){
					//cout<<"u "<<i + k * N<< " v: "<<j + (k + 1) * N<<endl;
					//cout<<"u "<<j + k * N<< " v: "<<i + (k + 1) * N<<endl;
					addEdge(i+N*k, j+N*(k+1), (1.0*w)/2.0);	
					addEdge(j+N*k, i+N*(k+1), (1.0*w)/2.0);
				}
			}
			//puts("");
		}
	}
	Dijkstra(1);
	pr("%.10lf", dis[2+N*K]);
	puts("");
}

int main()
{
	#ifndef ONLINE_JUDGE 
	FILE_OUT
	#endif
//	int T;sc("%d", &T);
//	while (T--) solve();
	solve();
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 51ms, 内存消耗: 9660K, 提交时间: 2023-04-02 19:08:34

#include <iostream>
#include <vector>
#include <queue>
#include <iomanip>

using namespace std;
using pr = pair<double, int>;

int n, k, vis[2510];
double f[2510], ans = 1000;
char c;
vector<pr> v[2510];
priority_queue<pr, vector<pr>, greater<pr>> pq;

void Record (int x, double lv) {
  if (vis[x]) {
    return ;
  }
  pq.push({lv, x});
}

void bfs () {
  Record(1, 0);
  while (!pq.empty()) {
    pr t = pq.top();
    pq.pop();
    if (vis[t.second]) {
      continue;
    }
    f[t.second] = t.first, vis[t.second] = 1;
    for (pr i : v[t.second]) {
      Record(i.second, i.first + t.first);
    }
  }
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n * (k + 1); i++) {
    f[i] = -1;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> c;
      if (i == j) {
        continue;
      }
      v[i].push_back({c - '0', j});
      for (int l = 1; l <= k; l++) {
        v[i + (l - 1) * n].push_back({(c - '0') / 2.0, j + l * n});
        v[i + l * n].push_back({c - '0', j + l * n});
      }
    }
  }
  bfs();
  for (int i = 0; i <= k; i++) {
    if (vis[i * n + 2]) {
      ans = min(ans, f[i * n + 2]);
    }
  }
  cout << fixed << setprecision(6) << ans;
  return 0;
}

C++(clang++11) 解法, 执行用时: 3ms, 内存消耗: 408K, 提交时间: 2020-11-04 19:30:56

#include<bits/stdc++.h>
using namespace std;
struct edge
{
	int pos;
	double val;
};
vector<edge>mp[60];
double dist[60][60];
bool vis[60][60];
struct node
{
	int now;
	int time;	
};
int n,k;
queue<node>que;
void spfa()
{
	que.push({1,k});vis[1][k]=true;dist[1][k]=0;
	while(que.size())
	{
		int x=que.front().now,t=que.front().time;
		que.pop();
		vis[x][t]=false;
		for(int i=0;i<mp[x].size();++i)
		{
			int y=mp[x][i].pos;double z=mp[x][i].val;
			if(dist[x][t]+z<dist[y][t])
			{
				dist[y][t]=dist[x][t]+z;
				if(!vis[y][t])
				{
					vis[y][t]=true;
					que.push({y,t});
				}
			}
			if(dist[x][t]+z/2<dist[y][t-1])
			{
				dist[y][t-1]=dist[x][t]+z/2;
				if(!vis[y][t-1])
				{
					vis[y][t-1]=true;
					que.push({y,t-1});
				}
			}
		}
	}
	cout<<dist[2][0]<<endl;
	return;
}
int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;++i)
	{
		for(int j=0;j<=k;++j)
		{
			dist[i][j]=(long long)1<<50;
		}
	}
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
			char ch;cin>>ch;
			mp[i].push_back({j,(double)ch-'0'});
		}
	}
	spfa();
}