POJ 1502(dijkstra+坑爹题意+坑爹输入)

               dijkstra+坑爹题意+坑爹输入  

 题意:

5
50
30 5
100 20 50
10 x x 10
第一个5代表五个点,接下来是5-1行。50代表第二个点到第一个点的距离。30是第三个点到第一个点的距离。5是第三个点到第二个点距离。以此类推。
x代表没有路,
  问:最短的路径
  思路:然后输入就很坑了(主要我菜)编译错好多次,用string输入,其他的没啥了

POJ 1502(dijkstra+坑爹题意+坑爹输入)

#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <vector>
//const int maxn = 1e5+5;
#define ll long long
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
//const int inf = 0x6fffffff;

#define MAX INT_MAX
#define FOR(i,a,b) for( int i = a;i <= b;++i)
#define bug cout<<"--------------"<<endl
using namespace std;
int ver[21000],edge[21000],head[21000],next[21000],d[21000],vis[21000];
int tot,n,m;
void add(int x,int y,int z)
{
    ver[++tot] = y,edge[tot] = z,next[tot] =head[x], head[x] = tot;
}
priority_queue<pair<int,int> >que;
void dijstra()
{
    memset(d,0x3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    d[1] = 0;
    que.push(make_pair(0,1));
    while(que.size())
    {

        int x=que.top().second; que.pop();
        if(vis[x] == 1) continue;
        vis[x] = 1;
        for(int i=head[x];i;i=next[i])
        {

            int y = ver[i],z=edge[i];
            if(d[y] > d[x] + z)
            {
                d[y] = d[x] +z;
                que.push(make_pair(-d[y],y));
            }
        }
    }
}
int hhh(string s)
{
    int ans=0;
    for(int i=0;i<s.length();++i)
    {
        ans=ans*10+s[i]-'0';
    }
    return ans;
}
int main()
{
//   freopen("C:\\Users\\方瑞\\Desktop\\input.txt","r",stdin);
//    freopen("C:\\Users\\方瑞\\Desktop\\output.txt","w",stdout);
      ios::sync_with_stdio(false);
      int n;
    cin>>n;
    for(int i=2;i<=n;++i)
    {
        for(int j=1;j<=i-1;++j)
        {
            string s;
            cin>>s;
            if(s[0] == 'x') continue;
            int ans = hhh(s);
            add(j,i,ans);
            add(i,j,ans);
        }
    }
    dijstra();
    int maxx=0;
    for(int i=1;i<=n;++i)
    {
        maxx = max(maxx,d[i]);
        //cout<<d[i]<<endl;
    }
    cout<<maxx<<endl;
}

 


上一篇:Golang, 以 9 个简短代码片段,切底弄懂 defer 的使用特点


下一篇:script标签属性sync和defer