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