PS： 题目就不描述了。。。
铭记：以后要记得好好读题，因为这浪费自己好多时间。
先上错误代码：
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <queue>
#include <set>
#include <iostream>
#include <string>
#include <fstream>
#include <stack>
//it's not a binary tree.
// So stupid.
using namespace std;
const int maxn =1e3+10;
const int INF=1e6+1;
int Map[maxn][maxn];
int dist[maxn];
int n,m;
bool vis[maxn];
struct node
{int data;int next;node(int x,int y): data(x),next(y){}
};
struct monde
{int pos,fare;
};
bool cmp(monde a,monde b)
{return a.fare <b.fare;
}
int result[maxn];
void dfs();
int main ()
{cin>>n;int i,j,k;//init//fill(vis,vis+n,0);for (i=0;i<n+1;i++)for (j=0;j<n+1;j++)Map[i][j]=INF;string a;for (i=2;i<=n;i++){for (j=1;j<i;j++){cin>>a;if(a=="x")continue;else{int len =a.size();int s =0;for (k=0;k<len;k++){s=s*10+(a[k]-'0');}Map[i][j]=Map[j][i]=s;}}}
// cout<<endl;right to print
// for (i=1;i<=n;i++)
// {
// for (j=1;j<=n;j++)
// if(Map[i][j]!=INF)
// cout<<Map[i][j]<<"\t";
// else
// cout<<"X\t";
// cout<<endl;
// }Map[1][1]=0;dfs();return 0;
}
void dfs()
{int maxx=0;queue<node>q;int i,j,k;q.push(node(0,1));int step=0;vis[1]=1;while (!q.empty()){first node is [1][1];node e=q.front();q.pop();
// cout<<endl;
// cout<<e.next<<endl;
// for (i=1;i<=n;i++)
// cout<<vis[i]<<" ";
// cout<<endl;monde pos[n];for(i=1;i<=n;i++){pos[i-1].pos=i;pos[i-1].fare=Map[i][e.next];}// cout<<" first"<<endl;
// for (i=0;i<n;i++)
// cout<<pos[i].pos<<" "<<pos[i].fare<<endl;sort(pos,pos+n,cmp);// cout<<" second"<<endl;
// for (i=0;i<n;i++)
// cout<<pos[i].pos<<" "<<pos[i].fare<<endl;int cnt =0;for (i=0;i<n;i++){if (!vis[pos[i].pos]&&pos[i].fare!=INF){vis[pos[i].pos]=1;q.push(node(pos[i].fare+e.data,pos[i].pos));cnt++;result[step++]=pos[i].fare+e.data;
// cout<<pos[i].pos<<" "<<pos[i].fare<<endl;}if(cnt==2)break;}}
// cout<<endl;for (i=0;i<step;i++)if(maxx<result[i])maxx=result[i];cout<<maxx<<endl;
}
ac 代码：
//#include <bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <map>
#include <deque>
#include <queue>
#include <set>
#include <iostream>
#include <string>
#include <fstream>
#include <stack>using namespace std;
const int maxn=1e3+1;
const int INF=1e6+1;
typedef long long ll;
int dist[maxn];
typedef pair<int,int>pp;
struct node
{int to,data;node(int x,int y): to(x),data(y){}
};
vector<node>g[maxn];int n,m;
///rememeber : using priority_queue to save time is a tool
/// dist[] is very important.void dijkstra(int st)
{fill(dist,dist+n+1,INF);// +n ==[0,n); +(n+1) ==[0,n];/// waint i,j,k;priority_queue<pp,vector<pp>,greater<pp> >q;
// while (!q.empty())
// q.pop();dist[st]=0;q.push(pp(0,st)); // 1 is data, 2 is the poswhile (!q.empty()){pp p=q.top();q.pop();int v=p.second;/// minif(p.first>dist[v])continue;int l =g[v].size();for (i=0;i<l;i++){node e =g[v][i];if(dist[e.to]>dist[v]+e.data){dist[e.to]=dist[v]+e.data;q.push(pp(dist[e.to],e.to));}}}
}
int main()
{int i,j,k;int x,y,z;cin>>n;string a;for (i=2;i<=n;i++){for (j=1;j<i;j++){cin>>a;if(a=="x")continue;else{int len =a.size();int s =0;for (k=0;k<len;k++){s=s*10+(a[k]-'0');}g[i].push_back(node(j,s));g[j].push_back(node(i,s));}}}dijkstra(1);int maxx =0;for (i=1;i<=n;i++)if (maxx<dist[i])maxx=dist[i];cout<<maxx<<endl;///initfor (i=0;i<n;i++)g[i].clear();return 0;
}
对于自己犯下的严重错误，罚2公里。。。。。。
我跑步去了。。。。。