题目链接: https://vjudge.net/problem/POJ-1502
dijkstra 板子题, 题目提供下三角情况, 不包含正对角线, 因为有题意都为 0, 处理好输入, 就是一个很水的题.
- #include
- #include
- #include
- #include
- #include
- #include
- using namespace std;
- typedef long long LL;
- #define inf (1LL <<30) - 1
- #define rep(i,j,k) for(int i = (j); i <= (k); i++)
- #define rep__(i,j,k) for(int i = (j); i <(k); i++)
- #define per(i,j,k) for(int i = (j); i>= (k); i--)
- #define per__(i,j,k) for(int i = (j); i> (k); i--)
- const int N = 110;
- vector<pair<int,int>> G[N];
- int val[N];
- int vis[N];
- int n;
- int fun(string& x){
- int sum = 0;
- rep__(i,0,(int)x.length()) sum = sum * 10 + (x[i] - '0');
- return sum;
- }
- void input(){
- string w;
- rep(i,2,n){
- rep__(j,1,i){
- cin>> w;
- if(w[0] == 'x') continue;
- int W = fun(w);
- G[i].push_back(make_pair(j,W));
- G[j].push_back(make_pair(i,W));
- }
- }
- }
- int dijkstra(){
- if(n == 1) return 0;
- val[1] = 0;
- rep(i,2,n) val[i] = inf;
- rep__(i,0,(int)G[1].size()) val[G[1][i].first] = G[1][i].second;
- vis[1] = true;
- rep(i,2,n){
- int x = -1;
- int v = inf;
- rep(j,1,n){
- if(!vis[j] && v> val[j]) v = val[x = j];
- }
- if(x == -1) continue;
- vis[x] = true;
- rep__(o,0,(int)G[x].size()){
- int v = G[x][o].first;
- int w = G[x][o].second;
- if(!vis[v] && val[v]> val[x] + w)
- val[v] = val[x] + w;
- }
- }
- int ans = 0;
- rep(i,2,n) ans = max(ans, val[i]);
- return ans;
- }
- int main(){
- iOS::sync_with_stdio(false);
- cin.tie(0);
- cin>> n;
- input();
- cout << dijkstra() << endl;
- getchar();getchar();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3129548.html