首页 > 代码库 > USACO comehome Dijkstra
USACO comehome Dijkstra
USER: Kevin Samuel [kevin_s1] TASK: comehome LANG: C++ Compiling... Compile: OK Executing... Test 1: TEST OK [0.003 secs, 3376 KB] Test 2: TEST OK [0.005 secs, 3376 KB] Test 3: TEST OK [0.005 secs, 3376 KB] Test 4: TEST OK [0.005 secs, 3376 KB] Test 5: TEST OK [0.011 secs, 3376 KB] Test 6: TEST OK [0.019 secs, 3376 KB] Test 7: TEST OK [0.035 secs, 3376 KB] Test 8: TEST OK [0.005 secs, 3376 KB] Test 9: TEST OK [0.008 secs, 3376 KB] All tests OK.YOUR PROGRAM (‘comehome‘) WORKED FIRST TIME! That‘s fantastic -- and a rare thing. Please accept these special automated
congratulations.
very easy, it‘s a shortest path problem
建图时直接以A-Z和a-z作为节点建图,我用了一个简单的Dijkstra算法,从Z 点反向找最近的点
/* ID:kevin_s1 PROG:comehome LANG:C++ */ #include <iostream> #include <cstdio> #include <string> #include <cstring> #include <vector> #include <map> #include <set> #include <algorithm> #include <cstdlib> #include <list> #include <cmath> using namespace std; #define MAXN 53 #define INF 99999 //gobal variable==== int P; int Graph[MAXN][MAXN]; int result; int Dist[MAXN]; int visited[MAXN]; //================== //function========== int Convert(char ch){ int index = -1; if(ch >= 'A' && ch <= 'Z'){ index = ch - 'A' + 1; } else if(ch >= 'a' && ch <= 'z'){ index = ch - 'a' + 27; } else index = -1; return index; } int Dijkstra(int v0){ int min; int k; //init for(int i = 1; i < MAXN; i++){ visited[i] = false; Dist[i] = Graph[v0][i]; } Dist[v0] = 0; visited[v0] = 1; for(int v = 1; v < MAXN; v++){ min = INF; for(int w = 1; w < MAXN; w++){ if(!visited[w] && (Dist[w] < min)){ min = Dist[w]; k = w; } } visited[k] = 1; for(int w = 1; w < MAXN; w++){ if(!visited[w] && (min + Graph[k][w] < Dist[w])){ Dist[w] = min + Graph[k][w]; } } } int Min = INF; for(int i = 1; i < MAXN; i++){ if(Dist[i] < Min && i >= 1 && i <= 26 && Dist[i] > 0){ Min = Dist[i]; result = i; } } return Min; } //================== int main(){ freopen("comehome.in","r",stdin); freopen("comehome.out","w",stdout); cin>>P; for(int i = 1; i < MAXN; i++){ Graph[i][i] = INF; for(int j = 1; j < MAXN; j++){ Graph[i][j] = INF; } } memset(visited, 0, sizeof(visited)); while(P--){ char chst, chen; int dist; cin>>chst>>chen>>dist; int st = Convert(chst); int en = Convert(chen); if(dist < Graph[st][en]){ Graph[st][en] = dist; Graph[en][st] = dist; } } int ans = Dijkstra(26); char chfarm = 'A' + result - 1; cout<<chfarm<<" "; cout<<ans<<endl; return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。