As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of
As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.
Input
Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (
Output
For each test case, print in one line two numbers: the number of different shortest paths between C1 and C2, and the maximum amount of rescue teams you can possibly gather.
All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.
Sample Input5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
Sample Output2 4
<code class=" hljs cpp"><span class="hljs-keyword">const</span> <span class="hljs-keyword">int</span> maxn = <span class="hljs-number">510</span>; <span class="hljs-keyword">int</span> ans, n, m, s, t, v[maxn], dis[maxn], mapPA[maxn][maxn], x, y, z, vis[maxn]; <span class="hljs-keyword">long</span> <span class="hljs-keyword">long</span> cnt[maxn]; <span class="hljs-comment">//n-城市数量,m-道路数量,s-起点,t-终点</span> <span class="hljs-keyword">void</span> dfs(<span class="hljs-keyword">int</span> x, <span class="hljs-keyword">int</span> y, <span class="hljs-keyword">int</span> z){ ans = max(ans, z); <span class="hljs-keyword">if</span> (x == y || dis[x] == -<span class="hljs-number">1</span>)<span class="hljs-keyword">return</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i < n; ++i){ <span class="hljs-keyword">if</span> (mapPA[x][i] != -<span class="hljs-number">1</span> && dis[x] == dis[i] + mapPA[x][i]){ dfs(i, y, z + v[i]); } } dis[x] = -<span class="hljs-number">1</span>; } <span class="hljs-keyword">void</span> PAT1003A(){ <span class="hljs-built_in">cin</span> >> n >> m >> s >> t; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i < n; ++i)<span class="hljs-built_in">cin</span> >> v[i]; <span class="hljs-built_in">memset</span>(mapPA, -<span class="hljs-number">1</span>, <span class="hljs-keyword">sizeof</span>(mapPA)); <span class="hljs-built_in">memset</span>(dis, -<span class="hljs-number">1</span>, <span class="hljs-keyword">sizeof</span>(dis)); <span class="hljs-keyword">while</span> (m--){ <span class="hljs-built_in">cin</span> >> x >> y >> z; mapPA[x][y] = mapPA[y][x] = z; } dis[s] = <span class="hljs-number">0</span>; cnt[s] = <span class="hljs-number">1</span>; <span class="hljs-keyword">while</span> (<span class="hljs-keyword">true</span>){ <span class="hljs-keyword">int</span> now = -<span class="hljs-number">1</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i < n; ++i){ <span class="hljs-keyword">if</span> (now == -<span class="hljs-number">1</span>)now = i; <span class="hljs-keyword">else</span> now = dis[now] < dis[i] ? now : i; } <span class="hljs-keyword">if</span> (now == -<span class="hljs-number">1</span>)<span class="hljs-keyword">break</span>; vis[now] = <span class="hljs-number">1</span>; <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i < n; ++i) { <span class="hljs-keyword">if</span> (mapPA[now][i] != -<span class="hljs-number">1</span>){ <span class="hljs-keyword">if</span> (dis[i] == -<span class="hljs-number">1</span> || dis[i] > dis[now] + mapPA[now][i]){ dis[i] = dis[now] + mapPA[now][i]; cnt[i] = cnt[now]; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (dis[i] == dis[now] + mapPA[now][i])cnt[i] += cnt[now]; } } } dfs(t, s, v[t]); <span class="hljs-built_in">cout</span> << cnt[t] << ans; } </code>
方法二:only 深搜
<code class=" hljs cpp"><span class="hljs-comment">//深搜+回溯</span> <span class="hljs-preprocessor">#define N 505</span> <span class="hljs-keyword">int</span> n, m, s, e; <span class="hljs-keyword">int</span> team[N]; <span class="hljs-keyword">int</span> numDis, minDis, maxTeam; <span class="hljs-keyword">int</span> vis[N]; <span class="hljs-keyword">int</span> matrix[N][N]; <span class="hljs-stl_container"><span class="hljs-built_in">vector</span><<span class="hljs-keyword">int</span>></span>path; <span class="hljs-keyword">void</span> DFS(<span class="hljs-keyword">int</span> next){ <span class="hljs-keyword">int</span> i; <span class="hljs-keyword">if</span> (next == e){ <span class="hljs-keyword">int</span> curTeam = <span class="hljs-number">0</span>, curDis = <span class="hljs-number">0</span>; <span class="hljs-keyword">for</span> (i = <span class="hljs-number">0</span>; i < path.size(); ++i){ curTeam += team[path[i]]; } <span class="hljs-keyword">for</span> (i = <span class="hljs-number">0</span>; i < path.size() - <span class="hljs-number">1</span>; ++i){ curDis += matrix[path[i]][path[i + <span class="hljs-number">1</span>]]; } <span class="hljs-keyword">if</span> (curDis < minDis){ numDis = <span class="hljs-number">1</span>; minDis = curDis; maxTeam = curTeam; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (curDis == minDis){ numDis++; <span class="hljs-keyword">if</span> (curTeam > maxTeam)maxTeam = curTeam; } <span class="hljs-keyword">return</span>; } <span class="hljs-keyword">for</span> (i = <span class="hljs-number">0</span>; i < n; ++i){ <span class="hljs-keyword">if</span> (matrix[next][i] != -<span class="hljs-number">1</span>){ <span class="hljs-keyword">if</span> (!vis[i]) { vis[i] = <span class="hljs-number">1</span>; path.push_back(i); DFS(i); path.pop_back(); vis[i] = <span class="hljs-number">0</span>; } } } } <span class="hljs-keyword">void</span> PAT1003A(){ <span class="hljs-keyword">int</span> i, a, b, d, j; <span class="hljs-keyword">while</span> (<span class="hljs-built_in">cin</span> >> n >> m >> s >> e) { <span class="hljs-keyword">for</span> (i = <span class="hljs-number">0</span>; i < n; i++, matrix[i][i] = <span class="hljs-number">0</span>, vis[i] = <span class="hljs-number">0</span>) { <span class="hljs-keyword">for</span> (j = <span class="hljs-number">0</span>; j < n; j++) { matrix[i][j] = -<span class="hljs-number">1</span>; } } <span class="hljs-keyword">for</span> (i = <span class="hljs-number">0</span>; i < n; i++) { <span class="hljs-built_in">cin</span> >> team[i]; } <span class="hljs-keyword">for</span> (i = <span class="hljs-number">0</span>; i < m; i++) { <span class="hljs-built_in">cin</span> >> a >> b >> d; matrix[a][b] = matrix[b][a] = d; } path.clear(); numDis = <span class="hljs-number">0</span>; minDis = <span class="hljs-number">0x7fffffff</span>; maxTeam = -<span class="hljs-number">1</span>; <span class="hljs-comment">//开始</span> vis[s] = <span class="hljs-number">1</span>; path.push_back(s); DFS(s); path.pop_back(); vis[s] = <span class="hljs-number">0</span>; <span class="hljs-built_in">cout</span> << numDis << <span class="hljs-string">" "</span> << maxTeam << endl; }</code>

この記事では、DockerのMySQLメモリ使用量を最適化することを調査します。 監視手法(Docker統計、パフォーマンススキーマ、外部ツール)および構成戦略について説明します。 これらには、Dockerメモリの制限、スワッピング、およびcgroupsが含まれます

この記事では、MySQLの「共有ライブラリを開くことができない」エラーについて説明します。 この問題は、必要な共有ライブラリ(.so/.dllファイル)を見つけることができないMySQLの障害に起因しています。ソリューションには、システムのパッケージMを介してライブラリのインストールを確認することが含まれます。

この記事では、MySQLのAlter Tableステートメントを使用して、列の追加/ドロップ、テーブル/列の名前の変更、列データ型の変更など、テーブルを変更することについて説明します。

この記事では、PHPMyAdminの有無にかかわらず、LinuxにMySQLを直接インストールするのとPodmanコンテナを使用します。 それは、各方法のインストール手順を詳述し、孤立、携帯性、再現性におけるポッドマンの利点を強調しますが、

この記事では、自己完結型のサーバーレスリレーショナルデータベースであるSQLiteの包括的な概要を説明します。 SQLiteの利点(シンプルさ、移植性、使いやすさ)と短所(同時性の制限、スケーラビリティの課題)を詳しく説明しています。 c

このガイドは、HomeBrewを使用してMacOSに複数のMySQLバージョンをインストールおよび管理することを示しています。 Homebrewを使用して設置を分離し、紛争を防ぐことを強調しています。 この記事では、インストール、開始/停止サービス、および最高のPRAを詳述しています

記事では、証明書の生成と検証を含むMySQL用のSSL/TLS暗号化の構成について説明します。主な問題は、セルフ署名証明書のセキュリティへの影響を使用することです。[文字カウント:159]

記事では、MySQLワークベンチやPHPMyAdminなどの人気のあるMySQL GUIツールについて説明し、初心者と上級ユーザーの機能と適合性を比較します。[159文字]


ホットAIツール

Undresser.AI Undress
リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover
写真から衣服を削除するオンライン AI ツール。

Undress AI Tool
脱衣画像を無料で

Clothoff.io
AI衣類リムーバー

AI Hentai Generator
AIヘンタイを無料で生成します。

人気の記事

ホットツール

mPDF
mPDF は、UTF-8 でエンコードされた HTML から PDF ファイルを生成できる PHP ライブラリです。オリジナルの作者である Ian Back は、Web サイトから「オンザフライ」で PDF ファイルを出力し、さまざまな言語を処理するために mPDF を作成しました。 HTML2FPDF などのオリジナルのスクリプトよりも遅く、Unicode フォントを使用すると生成されるファイルが大きくなりますが、CSS スタイルなどをサポートし、多くの機能強化が施されています。 RTL (アラビア語とヘブライ語) や CJK (中国語、日本語、韓国語) を含むほぼすべての言語をサポートします。ネストされたブロックレベル要素 (P、DIV など) をサポートします。

SublimeText3 英語版
推奨: Win バージョン、コードプロンプトをサポート!

Dreamweaver Mac版
ビジュアル Web 開発ツール

AtomエディタMac版ダウンロード
最も人気のあるオープンソースエディター

ゼンドスタジオ 13.0.1
強力な PHP 統合開発環境
