``` int ans=0x3f3f3f3f; ```

这行代码定义了一个整型变量ans，并将其赋值为0x3f3f3f3f。

0x3f3f3f3f在十六进制表示中是1061109567，在二进制表示中是00111111 00111111 00111111 00111111，共32位，也就是4个字节。由于是有符号整型，第一位为符号位（0表示正数，1表示负数），因此该数字在有符号整型中的值为-1061109568。

在算法竞赛中，将一个变量初始化为0x3f3f3f3f通常表示将其设为一个极大值，以便在求最小值时进行比较。因为该数字远大于int型所能表示的最大值2^31-1，所以在比较过程中不会被覆盖。

相关问题

#include <iostream> #include <cstdio> #include <queue> using namespace std; const int INF=0x3f3f3f3f;//无穷大 int n,ans=0; int g[105][105],dis[105],vis[105]; struct edge { int u,v,d;//边的起点、终点、权值 bool operator < (const edge &a) const { return d>a.d; } }; int main() { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { cin>>g[i][j]; if(g[i][j]==0) g[i][j]=INF; } priority_queue<edge> q;//优先队列 int temp=1,cnt=0;//当前顶点和边数 for(int i=1;i<=n;i++) { if(i!=temp) { dis[i]=g[temp][i]; q.push({temp,i,g[temp][i]}); } }//从结点1开始 while(!q.empty()) { edge t=q.top(); q.pop(); int u=t.u; int v=t.v; int d=t.d; if(vis[v]) continue;//已经在已加入点的集合当中 vis[v]=1; cnt++; cout<<v<<" "<<u<<" "<<d<<endl; //ans+=t.d; if(cnt==n-1) break; temp=v; for(int i=1;i<=n;i++) { if(!vis[i]&&g[temp][i]<dis[i]) { dis[i]=g[temp][i]; q.push({temp,i,g[temp][i]}); } }//更新优先队列 } //cout<<ans<<endl; return 0; } 将它改为用邻接表存储

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f;//无穷大
const int MAXN = 105;//最大结点数

int n, ans = 0;
vector<pair<int, int>> g[MAXN];//邻接表存储图
int dis[MAXN], vis[MAXN];

struct edge {
int u, v, d;//边的起点、终点、权值
bool operator < (const edge &a) const {
return d > a.d;
}
};

int main() {
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) {
int w;
cin >> w;
if (w != 0)
g[i].push_back(make_pair(j, w));
}
priority_queue<edge> q;//优先队列
int temp = 1, cnt = 0;//当前顶点和边数
for (int i = 0; i < g[temp].size(); i++) {
int v = g[temp][i].first;
int d = g[temp][i].second;
dis[v] = d;
q.push({ temp, v, d });
}//从结点1开始
while (!q.empty()) {
edge t = q.top();
q.pop();
int u = t.u;
int v = t.v;
int d = t.d;
if (vis[v]) continue;//已经在已加入点的集合当中
vis[v] = 1;
cnt++;
cout << v << " " << u << " " << d << endl;
//ans+=t.d;
if (cnt == n - 1) break;
temp = v;
for (int i = 0; i < g[temp].size(); i++) {
int j = g[temp][i].first;
int w = g[temp][i].second;
if (!vis[j] && w < dis[j]) {
dis[j] = w;
q.push({ temp, j, w });
}
}//更新优先队列
}
//cout<<ans<<endl;
return 0;
}

#include <iostream> #include <cstdio> #include <queue> using namespace std; const int INF=0x3f3f3f3f;//无穷大 int n,ans=0; int g[105][105],dis[105],vis[105]; struct edge { int u,v,d;//边的起点、终点、权值 bool operator < (const edge &a) const { return d>a.d; } }; int main() { cin>>n; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { cin>>g[i][j]; if(g[i][j]==0) g[i][j]=INF; } priority_queue<edge> q;//优先队列 int temp=1,cnt=0;//当前顶点和边数 for(int i=1;i<=n;i++) { if(i!=temp) { dis[i]=g[temp][i]; q.push({temp,i,g[temp][i]}); } }//从结点1开始 while(!q.empty()) { edge t=q.top(); q.pop(); int u=t.u; int v=t.v; int d=t.d; if(vis[v]) continue;//已经在已加入点的集合当中 vis[v]=1; cnt++; cout<<v<<" "<<u<<" "<<d<<endl; //ans+=t.d; if(cnt==n-1) break; temp=v; for(int i=1;i<=n;i++) { if(!vis[i]&&g[temp][i]<dis[i]) { dis[i]=g[temp][i]; q.push({temp,i,g[temp][i]}); } }//更新优先队列 } //cout<<ans<<endl; return 0; } 将它改为用邻接表存储

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

const int INF = 0x3f3f3f3f; //无穷大
int n, ans = 0;
vector<pair<int, int>> adj[105];
int dis[105], vis[105];

struct edge {
int u, v, d; //边的起点、终点、权值
bool operator < (const edge &a) const {
return d > a.d;
}
};

int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int w;
cin >> w;
if (w != 0) {
adj[i].push_back({j, w}); //添加边
}
}
}

priority_queue<edge> q; //优先队列
int temp = 1, cnt = 0; //当前顶点和边数
for (auto p : adj[temp]) {
int v = p.first, d = p.second;
dis[v] = d;
q.push({temp, v, d});
} //从结点1开始

while (!q.empty()) {
edge t = q.top();
q.pop();
int u = t.u, v = t.v, d = t.d;
if (vis[v]) continue; //已经在已加入点的集合当中
vis[v] = 1;
cnt++;
cout << v << " " << u << " " << d << endl;
//ans+=t.d;
if (cnt == n - 1) break;
temp = v;
for (auto p : adj[temp]) {
int i = p.first;
if (!vis[i] && p.second < dis[i]) {
dis[i] = p.second;
q.push({temp, i, p.second});
}
} //更新优先队列
}
//cout<<ans<<endl;
return 0;
}