fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // #define int long long
  5. using ll = long long;
  6. using ld = long double;
  7. #define el '\n'
  8. #define dbg(x) cout << #x << " = " << x << el
  9.  
  10. const int N=1e5+10;
  11. const ll INF=2e18;
  12. vector<ll> adj[N], cores(N), vis(N), peso(N), dist(N, INF);
  13.  
  14. void solve() {
  15.     int n, m, k; cin >> n >> m >> k;
  16.     for(int i = 1; i<= n; i++){
  17.         int a; cin >>a; peso[i]=a;
  18.     }
  19.     for(int i =0; i<m; i++){
  20.         int a, b; cin >>a >> b;
  21.         adj[a].push_back(b);
  22.         adj[b].push_back(a);
  23.     }
  24.  
  25.     priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
  26.  
  27.     pq.push(make_pair(peso[1], 1));
  28.     while (!pq.empty())
  29.     {
  30.         auto [p, v] = pq.top();
  31.         pq.pop();
  32.         if(vis[v]) continue;
  33.         vis[v]=1;
  34.  
  35.         for(auto x: adj[v]){
  36.             if(vis[x] || dist[x] < peso[x] + p) continue;
  37.             dist[x] = peso[x]+p;
  38.             pq.push({peso[x]+p, x});
  39.         }
  40.     }
  41.  
  42.  
  43.     set <int> st;
  44.     for(int i = 1; i<= n; i++) st.insert(i);
  45.     int flag = 0, comp= n-k;
  46.     for(auto x:adj[1]) if(x == n) flag = 1;
  47.  
  48.     if(flag && dist[n] == peso[1] + peso[n] && k == 1 && comp == 1){
  49.         cout << "impossible\n";
  50.         return;
  51.     } else if(flag && dist[n] == peso[1] + peso[n]){
  52.         if(k > 1){
  53.             cores[1] = cores[n] = 1;k-=2;
  54.             st.erase(1); st.erase(n);
  55.         } else{
  56.             cores[1] = cores[n] = 2;
  57.             st.erase(1); st.erase(n);
  58.         }
  59.     }
  60.  
  61.     // cout << dist[n]<<"\n";
  62.  
  63.  
  64.     if(k >= 1){
  65.         k--;
  66.         cores[1] = 1;
  67.         st.erase(1);
  68.         for(auto x: adj[1]){
  69.             if(!k) break;
  70.             cores[x] = 1;
  71.             k--;
  72.             st.erase(x);
  73.         }
  74.     }
  75.  
  76.     if(k >= 1){
  77.         k--;
  78.         cores[n] =1;
  79.         st.erase(n);
  80.         for(auto x: adj[n]){
  81.             if(!st.size() || st.find(x) == st.end()) continue;
  82.             if(!k) break;
  83.             k--;
  84.             st.erase(x);
  85.         }
  86.     }
  87.  
  88.     for(auto x: st) cores[x] = 2;
  89.     for(int i = 1; i<= n; i++){
  90.         if(cores[i] == 2) cout << "S";
  91.         else cout <<"N";
  92.     }
  93.     cout <<"\n";
  94.  
  95.  
  96. }
  97.  
  98. int32_t main() {
  99.     ios::sync_with_stdio(false);
  100.     cin.tie(nullptr);
  101.  
  102.     int ttt = 1;
  103.     // cin >> ttt;
  104.     while(ttt--) {
  105.         solve();
  106.     }
  107.     return 0;
  108. }
Success #stdin #stdout 0.01s 8672KB
comments (?)
stdin 
Standard input is empty
stdout 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			


			                        
			
			

				

	
					
					 https://ideone.com/olJIqH
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
21 hours ago

					

					

						
visibility:

						

							 public																												
							
							

								
							

						

					

										
										

					
					 Share or Embed source code
					
					
					
					

						
						
						
						
						
						
						
					

					
						
	
	
	
	
					
					
					
					
					 
					
					
					
					 
					
					
					
					
					
					

					

					

					
						
					

					


	
Discover > Sphere Engine API

	
The brand new service which powers Ideone!

	
	
Discover > IDE Widget

    
Widget for compiling and running the source code in a web browser!