結果

問題 No.1069 電柱 / Pole (Hard)
ユーザー m_9719
提出日時 2020-05-29 23:06:01
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,502 bytes
コンパイル時間 2,172 ms
コンパイル使用メモリ 183,688 KB
実行使用メモリ 815,028 KB
最終ジャッジ日時 2024-11-06 12:08:25
合計ジャッジ時間 4,500 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 2 WA * 1 MLE * 1 -- * 75
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define MOD (long long int)(998244353)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const long double PI  = acos(-1.0L);
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
typedef pair<double,double> PDD;
typedef pair<double,int> PDI;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
#define chmax(a,b) a = (((a)<(b))?(b):(a))
#define chmin(a,b) a = (((a)>(b))?(b):(a))

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

struct State {
    int n; double w;
    State(int n, double w) :
	n(n), w(w) {}
    bool operator < (const State &s) const {
	return w > s.w;
    }
};

struct Edge {
    int n; double w;
    Edge (int n, double w) :
	n(n), w(w) {}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
vector<double> ans;

int k_shortestPath(const Graph &g, int s, int e, int k) {
    int N = g.size();
    double dist[N];
    bool visited[N];
    for (int i = 0; i <= N; ++i) dist[i] = (double)LINF;
    dist[e] = 0.0;
    memset(visited, false, sizeof(visited));
    priority_queue<State> Q;
    Q.push(State(e, 0.0));
    while (!Q.empty()) {
			State cr = Q.top(); Q.pop();
			if (visited[cr.n]) continue;
			visited[cr.n] = true;
			for (int i = 0; i < g[cr.n].size(); ++i) {
		    Edge edg = g[cr.n][i];
		    if (visited[edg.n]) continue;
		    if (dist[edg.n] > cr.w + edg.w) {
					dist[edg.n] = cr.w + edg.w;
					Q.push(State(edg.n, cr.w + edg.w));
				}
			}
  	}
		// cerr<<R.top().w<<endl;
    int cnt = 0; // ゴールカウント
    priority_queue<State> R;
    /* priority_queue Rは
     * [それまでの距離＋そのノードからゴールまでの距離]
     * でソートされる。
     * これによりゴールに近い状態から取り出される
     */
    R.push(State(s, 0.0 + dist[s]));
    while (!R.empty()) {
			State cr = R.top(); R.pop();
			cr.w -= dist[cr.n]; // cr.wをそれまでの距離に戻す
			// cerr<< cr.w SP cnt<<endl;
			if (cr.n == e && ++cnt <= k) ans.PB(cr.w);
			if(cnt==k+1) return k;
			if(cr.n==e&&R.size()==0) return -1;
			// if(R.size()==0) return -1;
			// cerr<< cr.n SP cr.w SP cnt<<endl;
			// cerr<<R.size()<<endl;
			if(cr.n == e && cnt==k+1) return k;
			for (int i = 0; i < g[cr.n].size(); ++i) {
			    Edge edg = g[cr.n][i];
			    R.push(State(edg.n, cr.w + edg.w + dist[edg.n]));
			}
			// cerr<<R.size()<<endl;
			// if(k>1&&R.size()==1) return -1;
    }
    return -1;
}

int main() {
	int n,m,k; cin>>n>>m>>k;
	Graph g(n);
	int x,y; cin>>x>>y; x--; y--;
	vector<PDD> t;
	rep(i,n){
		double p,q; cin>>p>>q;
		t.PB(MP(p,q));
	}
	rep(i,m){
		int p,q; cin>>p>>q; p--; q--;
		double d=pow(pow(t[p].first-t[q].first,2.0)+pow(t[p].second-t[q].second,2.0),0.50);
		g[p].PB(Edge(q,d)); g[q].PB(Edge(p,d));
	}
	int ret=k_shortestPath(g, x, y, k);
	rep(i,ans.size()) cout<<ans[i]<<endl;
	rep(i,k-ans.size()) cout<<-1<<endl;


    // printf("%d\n", k_shortestPath(g, x, y, k));
}
0